Codeforces #1049 : Div2. E2. Prime Gaming (Hard Version)

本番にHardまで解けきれず…。
https://codeforces.com/contest/2140/problem/E2

問題

整数N,Mが与えられる。
整数列Aを、長さがNで各要素が1～Mのいずれかの整数値を取るものとする。
このようなAはM^N通りある。
それぞれについて以下の問題の解の総和を求めよ。

• 2人でターン制のゲームを行う。Aのうち削除できる要素番号が決まっている。
• 各人のターンでは、削除可能な番号の要素を1つ選び取り除く。数列の後ろの要素は前に詰まる。
• 最後|A|=1になったら終了する。先手はその値を最大化、後手は最小化したいとき、解は最後に残る値とする。

解法

各要素の具体的な要素は不要で、要素の大小関係だけ見ればよい。
先手はk以上、後手はk未満にしたい場合、初期状態で各要素がk以上か未満かに対するbitmaskが与えられたとき、k以上を達成できるかどうかはBitDPで求められる。

int T,N,M,K;
const ll mo=1000000007;

int F[21][1<<20];
int G[21][1<<20];
ll num[1<<20];
ll fact[21];
ll dp[21];
int C[21];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	FOR(i,20) fact[i+1]=fact[i]*(i+1)%mo;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>K;
		ZERO(C);
		FOR(i,K) {
			cin>>x;
			C[x-1]=1;
		}
		int mask;
		F[1][1]=G[1][1]=1;
		ZERO(dp);
		for(i=2;i<=N;i++) {
			FOR(mask,1<<i) {
				F[i][mask]=0;
				G[i][mask]=1;
				FOR(j,i) if(C[j]) {
					int mask2=(mask&((1<<j)-1)) | ((mask>>(j+1))<<j);
					if(G[i-1][mask2]==1) F[i][mask]=1;
					if(F[i-1][mask2]==0) G[i][mask]=0;
					
				}
			}
		}
		ZERO(C);
		FOR(mask,1<<N) if(F[N][mask]) C[__builtin_popcount(mask)]++;
		ll ret=0;
		for(i=1;i<=N;i++) {
			for(j=1;j<=M;j++) {
				(ret+=modpow(j-1,N-i)*modpow(M-j+1,i)%mo*C[i])%=mo;
			}
		}
		cout<<ret<<endl;
		
		
	}
}

まとめ

BitDPにはなるんだろうなぁと思いつつ、うまく持ち込めなかった。