yukicoder : No.1634 Sorting Integers (Multiple of K) Hard

シリーズ物の最終問題。
https://yukicoder.me/problems/no/1634

問題

正整数の集合を考える。
この集合に含まれる整数は、1～9の各数字が含まれる回数が指定されたものに一致するもの全通りである。
このうちMの倍数は何個あるか。

解法

総桁数が14なので、半分全列挙しよう。
上半分の桁と、下半分の桁を列挙し、それぞれmod Mでの登場回数をカウントして突き合わせればよい。

int N;
int K;
int C[10];
vector<int> D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,9) {
		cin>>C[i+1];
		FOR(x,C[i+1]) D.push_back(i+1);
	}
	
	if(N==1) {
		cout<<(D[0]%K==0)<<endl;
		return;
	}
	
	ll ret=0;
	int mask;
	map<int,ll> memo;
	
	ll up=1;
	FOR(i,N-N/2) up=up*10%K;
	
	FOR(mask,1<<N) if(__builtin_popcount(mask)==N/2) {
		map<int,ll> cand;
		
		ll val=0;
		vector<pair<int,int>> V,V2;
		FOR(i,N) {
			if(mask&(1<<i)) {
				val=val*10+D[i];
				V.push_back({i,D[i]});
			}
			else {
				V2.push_back({i,D[i]});
			}
		}
		
		if(memo.count(val)) {
			ret+=memo[val];
			continue;
		}
		
		ll pat=0;
		do {
			ll v=0;
			FORR(a,V) v=v*10+a.second;
			cand[v*up%K]++;
		} while(next_permutation(ALL(V)));
		
		do {
			ll v=0;
			FORR(a,V2) v=v*10+a.second;
			v=(K-v%K)%K;
			pat+=cand[v];
		} while(next_permutation(ALL(V2)));
		
		
		ret+=pat;
		memo[val]=pat;
		
	}
	
	FOR(i,10) {
		FOR(x,C[i]) ret/=(x+1);
	}
	
	cout<<ret<<endl;
	
}

まとめ

シリーズお疲れさまでした。