2012-02-18

Codeforces 107(Div2)

07:30 |

482 + 836 + 0(WA) + 692

Rank 294

1593→1594 微増..

C. Win or Freeze

07:30 |

Nvodskは寒いので、直前に書いた整数の自明でない約数を１つ紙に書いてその回数だけホテルの周りを走るゲームをするｗ

（ロシア企業(?)運営のサイトらしくていい）

約数を書けなくなった方が勝ち。最初に q ( <= 10**13) が書いてあって二人が最適なゲームをする場合、どっちが勝つか、最初(1)が勝つなら初手も出力する。

n が Win number か Lose number か計算する関数 f を書いた。

自明でない約数がなかったら Win.
ある場合、全ての約数 d に対して f(d)==Win なら何を選んでも Lose なので f(n)==Lose.
f(d)==Lose なる d がある場合、それを選べば Win になるので f(n)==Win

をメモ化再帰で。そしたら TLE になった。

（後ほど）

１つでも Lose があったら f(n)==Win に決定するのでそこで抜けて良いのに抜けてなかった。そこを抜けるようにしたら accepted.

しかし正解者のコードを見てるとみなさん再帰させてない。

この問題の場合はもっと簡単なロジックで答えがでるらしい。今のところ理解できず。

あと、こういう約数とか素数とかからむとオーダーがよくわからなくなる。

メモ化のキーの範囲は long long だけどうまく重複するので大丈夫とか、そのへん。

map<ll, int> memo;
ll move=0;
int f(ll n) {
	if(memo.count(n)) return memo[n];
	int allW=1;
	int win = 1;
	for(ll i=2;i*i<=n;i++) {
		if(n % i == 0) {
			int r0=f(i);
			int r1=f(n/i);
			allW &= r0;
			allW &= r1;
			if(!r0) move=i;
			if(!r1) move=n/i;
			win=0;
			if(!r0||!r1) return memo[n] = 1; //// ここ入れたら accepted
		}
	}
	int ret = win ? win : (allW ? 0 : 1);
	//cout<<n<<" "<<ret<<endl;
	return memo[n] = ret;
}

int main() {
	ll q;
	cin>>q;
	int r = f(q);
	cout<<(r?1:2)<<endl;
	if(r) cout<<move<<endl;
	
	return 0;
}

D. Quantity of Strings

07:30 |

長さ N で M 種類の文字を使った文字列のうち、どの長さ K の部分文字列も回文になっているようなものの個数を出す。

1 <= N,M,K <= 2000

N 頂点のグラフを考えて、同じでないといけない頂点を辺で結ぶ。それで、M の「連結な部分の数」乗が答え。

こういうグラフに帰着させるようなのは１年前はできなかった気がする。よかよか。

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

int main() {
	int n, m, k;
	cin>>n>>m>>k;
	
	//if(n<k) {
	//	cout<<0<<endl;
	//	return 0;
	//}
	UnionFind uf(n);
	REP(i, n-k+1) {
		REP(j, k/2) {
			uf.unionSet(i+j, i+k-1-j);
		}
	}
	map<int, int> mm;
	REP(i, n) {
		mm[uf.root(i)]=1;
	}
	ll ans=1;
	REP(i, mm.size()) {
		ans *= m;
		ans = ans % 1000000007LL;
	}
	cout<<ans<<endl;
	
	return 0;
}