Particle

競技プログラミングについての雑記

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;
	}
};