TopCoder SRM 572 Div2 Hard DistinctRemainders

さてHard。
http://community.topcoder.com/stat?c=problem_statement&pm=12384

問題

大きな整数Nと、高々50の整数Mが与えられる。
和がNであり、各要素をMで割った余りが互いに異なるような数列を作るとき、そのような組み合わせの数を答える。

解法

まず、余りに注目して、余りが0～(M-1)のものをX個足して合計がYになるような組み合わせの数をDPで求める。
この処理はO(M^3)なので、計算量は問題ない。

次に、余りをX個足してYになる組み合わせ数がDPで求まっているので、残された(N-Y)を余りの値を変えないようにこのX個に振り分ける数を求める。
つまり、(N-Y)%M==0の場合に(N-Y)/M個のMをX個に振り分けるので、C( (N-Y)/M + X - 1, X-1)通りの組み合わせがある。
また、このX個の並び順は任意なのでX!を掛ければよい。

Combinationのやり方は、Xが高々50だし返す値は1000000007の剰余なので、割り算を逆元の乗算にする方法を取ればよい。

ll MO=1000000007;
ll combi(ll N_, ll C_) {
	int i;
	const int num=100;
	static ll rev[num+1],revt[num+1];
	
	if(rev[1]==0) {
		rev[1]=1; for(i=2;i<=num;i++) rev[i]=rev[MO%i]*(MO-MO/i)%MO;
		revt[0]=1; for(i=1;i<=num;i++) revt[i]=revt[i-1]*rev[i]%MO;
	}
	ll ret=revt[C_];
	FOR(i,C_) ret = (ret * ((N_-i)%MO))%MO;
	return ret;
}

class DistinctRemainders {
	public:
	int howMany(long long N, int M) {
		int i,x,y,sum=0;
		ll dp[50*51/2+2][51];
		ll P[60];
		
		ZERO(dp);
		dp[0][0]=1;
		
		sum=0;
		FOR(i,M) {
			for(x=sum;x>=0;x--) for(y=i;y>=0;y--) dp[x+i][y+1] = (dp[x+i][y+1]+dp[x][y])%MO;
			sum+=i;
		}
		
		P[0]=1;
		FOR(x,M) P[x+1]=(P[x]*(x+1))%MO;
		
		ll res=0;
		FOR(x,sum+1) {
			if(x>N) continue;
			if((N-x) % M) continue;
			ll H=(N-x)/M;
			for(y=1;y<=M;y++){
				if(dp[x][y]){
					res = (res+((dp[x][y]*P[y])%MO)*combi(H+y-1,y-1)) % MO;
				}
			}
		}
		
		return res;
	}
};

まとめ

逆元を使ったCombinationの計算方法はだいぶ慣れてきたな。