Codeforces #188 Div1. D. Game with Powers

本番には解ききれなかったけど、後日初めて自力で解けたD。
http://codeforces.com/contest/317/problem/D

問題

数Nに対し、初期状態で1～Nの数字がすべてある。
この数値群を用いて2人でゲームを行う。
両者各ターンで以下の手順を行う。

• 数字群の残りが0個なら負け。
• 残された数値群から１つxを選んだ場合、x、x^2、x^3...を数値群から取り除く。

両者が最適手を取ったとき、勝者はどちらになるか答えよ。

解法

Grundy数とNimの問題。

まず、他の数の累乗数にならないxに対し、N以下の数列からなる{x,x^2,x^3,...,x^p}を何個とれるか数える。
後はxは関係なく、要素数がpの数列が何個あるか、だけを考えればよい。

あとは、{x,x^2,x^3,...,x^p}に対しGrundy数をカウントする。
{x,x^2,x^3,...,x^p}からx^tを選び、{x^t、x^2t、x^3t....}を取り除きなら各状態のGrundy数を決めていけばよい。

N<=10^9なので、pは最大29なのだが、この時上記処理で移動可能な遷移は70万ちょいあり、また手元で計算したら2秒程度かかった。
これでは本番TLEする。

ただ、{x,x^2,x^3,...,x^p}から遷移可能な状態のうち、最終的に必要なのはG[t]={x,x^2,x^3,...,x^t}のGrundy数だけで、途中が歯抜けになった数列は必要ない。
なのでGrundy数は2秒かけて事前計算した値(下記コードのコメントアウト部およびcalc)を使えばよい。

int N;
int G[50],GR[50];
int BM[32];
int vis[100002];
map<int,int> gra;

int calc(int v) {
	int mask=0,i,j;
	if(gra.find(v)!=gra.end()) return gra[v];
	
	mask=j=1;
	for(i=2;(1<<i) <= v; i++) if(v & (1<<i)) mask |= 1<<calc(v & BM[i]);
	while(mask & (1<<j)) j++;
	return gra[v]=j;
}

void solve() {
	int f,r,i,j,k,l, x,y;
	ll t;
	
	N=GETi();
	for(i=2;i<32;i++) {
		BM[i]=0x7FFFFFFF;
		for(j=i;j<=31;j+=i) BM[i] ^= 1<<j;
	}
	G[1]=N;
	
	for(i=2;i<=min(100000,N);i++) {
		G[1]--;
		if(vis[i]) continue;
		
		j=1;
		ll t=i;
		while(t*i<=N) t*=i,j++,vis[min(100001LL,t)]++;
		G[j]++;
	}
	
	/*
	// output table
	gra[0]=0;
	calc(0x3FFFFFFE);
	FOR(i,32) _P("%d %d\n",i,gra[(1<<(i+1))-2]);
	*/
	GR[1]=1;
	GR[2 ]=2;
	GR[3 ]=1;
	GR[4 ]=4;
	GR[5 ]=3;
	GR[6 ]=2;
	GR[7 ]=1;
	GR[8 ]=5;
	GR[9 ]=6;
	GR[10]= 2;
	GR[11]= 1;
	GR[12]= 8;
	GR[13]= 7;
	GR[14]= 5;
	GR[15]= 9;
	GR[16]= 8;
	GR[17]= 7;
	GR[18]= 3;
	GR[19]= 4;
	GR[20]= 7;
	GR[21]= 4;
	GR[22]= 2;
	GR[23]= 1;
	GR[24]= 10;
	GR[25]= 9;
	GR[26]= 3;
	GR[27]= 6;
	GR[28]= 11;
	GR[29]= 12;

	int nim=0;
	FOR(i,32) if(G[i]%2) nim ^= GR[i];
		
	if(nim==0) _P("Petya\n");
	else _P("Vasya\n");
	
	return;
}

まとめ

Dにしては簡単だったね。