AtCoder ARC #134 : E - Modulo Nim

Dで手間取ったせいで間に合わず…。
https://atcoder.jp/contests/arc134/tasks/arc134_e

問題

N個の整数変数を使った2人対戦ゲームを行う。
現在の全変数の最大値をXとする。

• Xが0なら、その時手番の方が勝ち
• Xが正の場合、プレイヤーは1～Xの範囲の整数mを選ぶ。全変数xを、x%mで置き換える。

N個の変数の初期値が、それぞれ1～A[i]のいずれかであるとする。
そのような組み合わせはProd(A)個あるが、うち先手必勝のものは何通りか。

解法

まず手番のプレイヤーが必敗のパターンを考える。
自分は実験で探索したが、理屈でも求められるようだ。
変数中の正整数の集合が：

• 1要素の場合、{1}か{2}
• 2要素の場合、{4,8}
• 3要素以上の場合、いずれも12の倍数

Aの最大値が200であることから、12の倍数で現れるのは高々12～192の16通りしかない。
そこで、3つ目のパターンは最初に(2^16)通り総当たりして、必ず負けるパターンを列挙してしまおう。

そうすると、結果初期状態として1,2,4,8,(12の倍数16通り),それ以外,の21種類のうち1個以上もっているのがどれかで先手必勝・必敗がわかる。
あとは(2^21)通りの状態についてDPで数え上げて行こう。
実際(2^21)通りのうち、多くの状態は必敗が確定するので、そのようなものは速めに1つの状態にまとめることで定数倍高速化できる。
というかそうしないとTLに収めるのが割と厳しかった。

int N,A[202];
const ll mo=998244353;

ll from[1<<21];
ll to[1<<21];
int table[202];
int win[1<<16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	win[0]=1;
	for(int mask=1;mask<1<<16;mask++) {
		int ma=0;
		FOR(i,16) if(mask&(1<<i)) ma=(i+1)*12;
		for(x=1;x<=ma;x++) {
			int mask2=0;
			set<int> S;
			FOR(i,16) if(mask&(1<<i)) {
				y=(i+1)*12%x;
				if(y%12) {
					S.insert(y);
				}
				else {
					if(y) mask2|=(1<<(y/12-1));
				}
			}
			if(S.size()) {
				if(mask2) continue;
				if(S.size()==1&&*S.begin()==1) win[mask]=1;
				if(S.size()==1&&*S.begin()==2) win[mask]=1;
				if(S.size()==2&&*S.begin()==4&&*S.rbegin()==8) win[mask]=1;
			}
			else {
				if(win[mask2]==0) win[mask]=1;
			}
		}
	}
	
	
	FOR(i,201) table[i]=20;
	FOR(i,16) table[(i+1)*12]=i;
	table[1]=16;
	table[2]=17;
	table[4]=18;
	table[8]=19;
	
	int mask;
	cin>>N;
	from[0]=1;
	FOR(i,N) {
		cin>>x;
		
		ZERO(to);
		int C[21]={};
		for(j=1;j<=x;j++) C[table[j]]++;
		
		FOR(mask,1<<21) if(from[mask]) FOR(j,21) to[mask|(1<<j)]+=from[mask]*C[j];
		ZERO(from);
		FOR(mask,1<<21) {
			x=((mask&65535)>0)+((mask&(1<<16))>0)+((mask&(1<<17))>0)+((mask&(3<<18))>0)+((mask&(1<<20))>0)*2;
			if(x>1) {
				(from[1<<20]+=to[mask])%=mo;
			}
			else {
				(from[mask]+=to[mask])%=mo;
			}
		}
	}
	
	
	ll ret=0;
	FOR(mask,1<<21) ret+=from[mask];
	FOR(mask,1<<16) if(win[mask]==0) ret+=mo-from[mask];
	ret+=mo-from[1<<16];
	ret+=mo-from[1<<17];
	ret+=mo-from[3<<18];
	cout<<ret%mo<<endl;
	
}

まとめ

Dで躓かなければ解き切れたのに…。