AGC016F: Games on DAG

https://agc016.contest.atcoder.jp/tasks/agc016_f

やっぱりできることとできないことの差がまだわからない…。

1と2のgrundy数が一致しないようなグラフを数え上げればいいです。
全ての頂点についてgrundy数を決めてしまえば、グラフを数え上げるのは多項式でできます。
今回grundy数はたかだか3なので、これで枝切りして通している人もいますが、まともにやる方法もあります。

grundy数が0の頂点の集合、1の集合、2の集合…と順番に取っていくことを考えます。
そこまでわかれば後は前処理を適当にとっておけばよくあるO(3^N)のDPになって通ります。

連結成分内でgrundy数を数え上げてやろうという方針をとって、全ての頂点が連結しているか包除原理で求めようとしたんですが、1を含む集合、2を含む集合、どっちも含む集合で非対称性があってできませんでした。

包除原理はやはり式に本質があると思うので、式にできない時は諦めるべきでしたね。

やっぱり想定解はすっきりした考察をしているであろうという仮定のもと問題を解きにいったほうがいいですね。

int N, M;
int G[15][15];

int to[15][(1 << 15)];
ll dp[(1 << 15)];
ll pow2[1000];

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b; cin >> a >> b; a--; b--;
		G[a][b] = 1;
	}

	pow2[0] = 1;
	rep(i, 0, 500) pow2[i + 1] = pow2[i] * 2 % mod;

	rep(i, 0, N) {
		rep(bit, 0, (1 << N)) {
			if((bit & (1 << i))) continue;
			int tmp = 0;
			rep(j, 0, N) {
				if(!(bit & (1 << j))) continue;
				tmp += G[i][j];
			}
			to[i][bit] = tmp;
		}
	}
	dp[0] = 1;
	rep(q, 0, (1 << N)) {
		for(int bit = q; bit; bit = (bit - 1) & q) {
			if((bit & (1 << 0)) && (bit & (1 << 1))) continue;
			int pbt = bit ^ q;
			int rbt = (1 << N) - 1 - q;
			ll mul = 1;
			ll cnt = 0;
			rep(i ,0, N) {
				if(!(rbt & (1 << i))) continue;
				MUL(mul, pow2[to[i][bit]] - 1);
			}
			rep(i, 0, N) {
				if(!(pbt & (1 << i))) continue;
				ADD(cnt, to[i][bit]);
			}
			// debug(bitset<3>(q), bitset<3>(pbt), bitset<3>(bit), bitset<3>(rbt), dp[pbt], mul, cnt);
			ADD(dp[q], dp[pbt] * mul % mod * pow2[cnt] % mod);
		}
		// debug(bitset<3>(q), dp[q]);
	}
	cout << dp[(1 << N) - 1] << "\n";
}