Codeforces #235 Div2. D. Roman and Numbers

ちょっと苦戦したけど何とか解けた。
http://codeforces.com/contest/401/problem/D

問題

数NとMが与えられるので、以下の条件を満たす数Xが何通りあるか答えよ。

• XはNの各桁を並べ替えて得られる数である。ただしleading zeroは不可。
• XはMで割り切れる。

解法

Nのうち何桁目を使用済みかをbitmaskで管理し、上の桁から埋めていけばよい。
状態としては(使用済み桁bitmask,現在のMの余り)を持ち、その状態を満たす数をbitDPで求める。

Nが最大18桁、X<=100なので、状態数は(2^18)*100、ループ回数は18*(2^18)*100もかかったが、なんとか1.9sで完了する。

なお、18桁もあれば同じ数字もいくつか登場するので、それらをまとめて処理すればもう少し高速化できる。

ll N,M;
vector<ll> V;
ll powd[10][20];
ll dpdp[1<<18][101];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	ll a=N;
	while(a) V.push_back(a%10),a/=10;
	
	FOR(i,10) {
		powd[i][0]=i;
		FOR(j,18) powd[i][j+1]=powd[i][j]*10;
		FOR(j,19) powd[i][j]%=M;
	}
	dpdp[0][0]=1;
	for(int mask=0;mask<1<<V.size();mask++) {
		int num=__builtin_popcount(mask);
		FOR(i,V.size()) {
			if(mask & (1<<i)) continue;
			if(i==V.size()-1 && V[num]==0) continue;
			l = powd[V[num]][i];
			FOR(j,M) {
				dpdp[mask | (1<<i)][(j+l)%M] += dpdp[mask][j];
			}
		}
	}
	
	ll ret=dpdp[(1<<V.size())-1][0];
	int num[10];
	ZERO(num);
	ITR(it,V) num[*it]++;
	FOR(i,10) if(num[i]) {
		FOR(j,num[i]) ret /= (j+1);
	}
	
	_P("%lld\n",ret);
}

まとめ

18*(2^18)*100はTLEするかと思ったけど間に合った。
この問題は上限4秒だし、これ想定解かな。