SRM 666 Div1 Medium SumOverPermutations
左端のビンから考え、DP をする。
dp[i: i 番目のビン][j: i 番目のビンは、左の i 個のビンの中で j 番目に使われる][k: (i+1)番目のビンが i 番目のビンよりあとなら 1、そうでないなら 0] ::= 条件を満たす状態数
とし、累積和を計算しながら DP を計算する。
#define N 4010 int dp[N][N][2]; class SumOverPermutations { public: int findSum(int n) { if(n==1) return 1; mset(dp, 0); dp[0][1][0] = 1; for(ll i = 1; i <= n; i++){ for(ll j = 0, sum = 0; j < i; j++){ (sum+=dp[i-1][j][1])%=mod; (dp[i][j+1][0]+=sum*(n-2)%mod)%=mod; (dp[i][j+1][1]+=sum*(n-1)%mod)%=mod; } for(ll j = i, sum = 0; j > 0; j--){ (sum+=dp[i-1][j][0])%=mod; (dp[i][j][0]+=sum*(n-1)%mod)%=mod; (dp[i][j][1]+=sum*(n)%mod)%=mod; } } ll res = 0; rep(i, n+1) (res+=dp[n][i][1])%=mod; return (res+mod)%mod; } };