ARC087 - omochan's diary

https://arc087.contest.atcoder.jp/

C
はい。
D
XY独立にできます。
E
本質っぽいgrundyのところまではわかったけどtrie木で敗北しました。
まずstringを2分木に対応させます。そうするといろいろな高さの2分木から頂点を取るゲームになります。
高さがdの2分木のgrundy数はdを2で割り切れる回数+1となるのであとは、trie木で片方しか頂点がない頂点を探せばいいです。

ll L;

int div(ll a) {
	int cnt = 0;
	while(a % 2 == 0) {
		cnt++;
		a /= 2;
	}
	return cnt;
}
struct trie {
	int G[MAX_N][2];
	int A[100];
	int M;

	trie() { init(); }
	void init() {
		memset(G, -1, sizeof(G));
		M = 1;
	}

	void add(const string& str) {
		int n = sz(str);
		int v = 0;
		rep(i, 0, n) {
			int y = str[i] - '0';
			if(G[v][y] == -1) {
				G[v][y] = M++;
			}
			v = G[v][y];
		}
	}
	void show() {
		rep(i, 0, 10) {
			debug(i, G[i][0], G[i][1]);
		}
	}

	void dfs(int v, int d) {
		// debug(v, d);
		int cnt = 0;
		if(G[v][0] != -1) {
			dfs(G[v][0], d + 1); 
			cnt++;
		}
		if(G[v][1] != -1) {
			dfs(G[v][1], d + 1);
			cnt++;
		}
		if(cnt == 1) {
			if(L - d >= 1) A[div(L - d)]++;
		}
	}
	bool win() {
		dfs(0, 0);
		rep(i, 0, 70) {
			if(A[i] % 2) return true;
		}
		return false;
	}
};

int N;
trie T;
string str[MAX_N];

void solve() {
	cin >> N >> L;
	rep(i, 0, N) {
		cin >> str[i];
		T.add(str[i]);
	}
	if(T.win()) {
		cout << "Alice\n";
	}
	else cout << "Bob\n";
}

これは初手がわからないと詰むパターンですね…

Σd(k,pk)=Σd(root,k)+d(root,pk)-2d(root, lca(k, pk))ですが、Σd(root,k)+d(root,pk)は一定なので、d(root, lca(k, pk))を最小化すればいいです。
さらにd(root, lca(k, pk)) = 0 <=> rootは重心が成立します。ここが難しいです。まあ木上での距離の和=>重心つかうは定石なんだけども。
証明はそんな大変じゃないです。少し試せばわかります。

重心が２つの時は単純で答えは((N/2)!)^2です。
重心が1つの時、lca(k,pk)!=rootとなるようなパーミュテーションを全体から引きたいので包除原理をします。
重心から生えてる木をT1...,TKとすれば
x1<=T1, ... xK<=TK、Σxi=xとすれば、求める値は

Σ(x=0→N-1)(-1)^x(N-x)! {Σ(x1,x2...xK)Π(k=1→K)C(Tk, xk)^2 xk!}となります。
この{}内をdp[i][x]:=Σ(k=0...i)xi = xの時のΣ(x1,x2...xi)Π(k=1→i)C(Tk, xk)^2 xk! と定義して求めます。
一見O(N^3)に見えますが、よくある木dpのようにO(N^2)となって間に合います。

int N;
vector<int> cen;
vector<int> G[MAX_N];
ll dp[2][MAX_N];

int search_centroid(int v, int p) {
	int s = 1, m = 0;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(p == n) continue;
		int t = search_centroid(n, v);
		s += t;
		MAX(m, t);
	}
	MAX(m, N - s);
	if(m <= N / 2) {
		cen.pb(v);
	}
	return s;
}

void solve() {
	cin >> N;
	C_init(N);
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[b].pb(a);
		G[a].pb(b);
	}
	search_centroid(0, -1);
	if(sz(cen) == 2) {
		cout << fac[N / 2] * fac[N / 2] % mod << "\n";
	}
	else if(sz(cen) == 1) {
		int c = cen[0];
		vector<int> vec;
		rep(i, 0, sz(G[c])) {
			int n = G[c][i];
			vec.pb(search_centroid(n, c));
		}
		int K = sz(vec);
		dp[0][0] = 1;
		int s = 0;
		int now = 0, next = 1;
		rep(i, 0, K) {
			memset(dp[next], 0, sizeof(dp[next]));
			rep(j, 0, s + 1) {
				if(!dp[now][j]) continue;
				int t = vec[i];
				rep(k, 0, t + 1) {
					ADD(dp[next][j + k], dp[now][j] * C(t, k) % mod * C(t, k) % mod * fac[k] % mod);
				}
			}
			s += vec[i];
			swap(now, next);
		}
		ll ans = 0;
		rep(i, 0, N) {
			if(i % 2) ADD(ans, mod - fac[N - i] * dp[now][i] % mod);
			else ADD(ans, fac[N - i] * dp[now][i] % mod);
		}
		cout << ans << "\n";
	}
}

sugimさんみたいに数式を効率良くつかって解けるようになりたいね。