题解：P16930 拱辰封仪

2026/6/18 17:52:55

难点在于会 NTT。

尝试刻画 \(x,y\) 之间存在长度为奇数的路径的条件。显然 \(x,y\) 要在同一个连通块中。注意到若连通块中存在奇环，则任取一条路径走奇环即可改变其长度奇偶性，因此一定存在长度为奇数的路径；若连通块为二分图，则存在长度为奇数的路径当且仅当 \(x,y\) 在二染色后异色。

把 \(E^2-O^2\) 转化成求 \((E+O)(E-O)\)。

先求 \(E+O\)，也就是求总方案数。对每个连通块构造多项式：

若连通块不为二分图，设共有 \(c\) 个点，构造多项式 \(1+cx\)。
若连通块为二分图，设二染色后有 \(c_0\) 个左部点，\(c_1\) 个右部点，构造多项式 \((1+x)^{c_0}+(1+x)^{c_1}-1\)。

把每个连通块对应的多项式分治乘起来即可。

再求 \(E-O\)，相当于求所有方案的 \((-1)^{\sum a_i}\) 之和。类似地对每个连通块构造多项式：

若连通块不为二分图，设有 \(c_0\) 个点点权为偶数，\(c_1\) 个点点权为奇数，构造多项式 \(1+(c_0-c_1)x\)。
若连通块为二分图，设二染色后，左部点中点权为偶数/奇数的点有 \(c_{0,0/1}\) 个，右部点中点权为偶数/奇数的点有 \(c_{1,0/1}\) 个，构造多项式 \((1+x)^{c_{0,0}}(1-x)^{c_{0,1}}+(1+x)^{c_{1,0}}(1-x)^{c_{1,1}}-1\)。

同样分治乘即可。

时间复杂度为 \(\mathcal{O}(n\log^2{n})\)。

主要代码

poly binom1(int n) {poly H(n + 1);for (int i = 0; i <= n; ++i) H[i] = C(n, i);return H;
}poly binom2(int n) {poly H(n + 1);for (int i = 0; i <= n; ++i) H[i] = C(n, i) * (i & 1 ? -1 : 1);return H;
}poly solve(const vector<poly> &vec, int l, int r) {if (l == r) return vec[l];int mid = l + r >> 1;return mul(solve(vec, l, mid), solve(vec, mid + 1, r));
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m >> k;init(n);for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= m; ++i) {int u, v;cin >> u >> v;G[u].emplace_back(v);G[v].emplace_back(u);}fill(c + 1, c + n + 1, -1);int id = 0;for (int x = 1; x <= n; ++x) {if (c[x] != -1) continue;++id;bool suc = true;array<int, 2> cntCol;array<array<int, 2>, 2> cntVal;cntCol.fill(0);for (auto &arr : cntVal) arr.fill(0);auto dfs = [&](auto &&self, int u) -> void {++cntCol[c[u]];++cntVal[c[u]][a[u] & 1];for (auto v : G[u]) {if (c[v] == -1) {c[v] = c[u] ^ 1;self(self, v);} else if (c[u] == c[v]) {suc = false;}}};c[x] = 0;dfs(dfs, x);poly p1, p2;if (!suc) {p1 = {1, cntCol[0] + cntCol[1]};p2 = {1, cntVal[0][0] + cntVal[1][0] - cntVal[0][1] - cntVal[1][1]};} else {p1 = add(binom1(cntCol[0]), binom1(cntCol[1]));p1[0] -= 1;p2 = add(mul(binom1(cntVal[0][0]), binom2(cntVal[0][1])),mul(binom1(cntVal[1][0]), binom2(cntVal[1][1])));p2[0] -= 1;}F1.emplace_back(p1);F2.emplace_back(p2);}auto H1 = solve(F1, 0, F1.size() - 1);auto H2 = solve(F2, 0, F2.size() - 1);mint val1 = k < H1.size() ? H1[k] : 0, val2 = k < H2.size() ? H2[k] : 0;cout << val1 * val2;return 0;
}