比赛传送门: Goodbye Jihai http://uoj.ac/contest/50 .
\(\Huge{\mathbf{再见, 己亥.\\ 你好, 庚子!\\ 祝大家新春快乐!}}\)
A. 新年的促销 http://uoj.ac/contest/50/problem/495
咕.
B. 新年的新航线 http://uoj.ac/contest/50/problem/496
咕.
C. 新年的复读机 http://uoj.ac/contest/50/problem/497
咕.
D. 新年的追逐战 http://uoj.ac/contest/50/problem/498
不难发现题目中定义的图乘积运算满足交换律和结合律.
对于所有 \(n\) 个图的总乘积 \(H = G_1 \times G_2 \times \cdots \times G_n = \langle V^*, E^* \rangle\), 有:
\(V^* = \{ \langle a_1, a_2, \ldots, a_n \rangle \: | \: a_i \in V_i \}\), 以及
两点 \(\langle a_1, a_2, \ldots, a_n \rangle\) 与 \(\langle b_1, b_2, \ldots, b_n \rangle\) 之间有连边, 当且仅当对于每个 \(1 \le i \le n\), 都有 \(\langle a_i, b_i \rangle \in E_i\).
考虑 \(H\) 的连通块性质. 通过手玩一些简单情况, 可以总结归纳:
首先, 在每一个原图 \(G_i\) 上都放置一个棋子, 第 \(i\) 个棋子在 \(G_i\) 的点 \(a_i\) 上, 那么 \(H\) 中与 \(u = \langle a_1, a_2, \ldots, a_n \rangle\) 邻接的一条边就相当于每个图上的棋子都走恰好一步.
可以得出, 如果这之中某一个棋子在孤立点上, 那么 \(u\) 就不存在邻接边.
对于其它的情况, 显然第 \(i\) 个棋子能够移动的范围就是 \(G_i\) 中 \(a_i\) 所在的连通块的所有点.
因为每个连通块都不是孤立点, 所以棋子可以无限移动. 因为连通块之间是独立的, 接下来假设 \(n = 2\), 即只计算两个连通块的乘积:
如果两个连通块都是二分图, 则它们的乘积恰好是 \(2\) 个二分图.
证明: 为这两个连通块中的点进行黑白染色, 则如果两个棋子所在的初始节点同色, 则任意移动都是同色的, 否则都是不同色的. 而且不难证明, 两种情况中的点都分别连通. 而因为棋子要回到初始点必然要走偶数步, 所以也不存在奇环, 是二分图.
如果其中一个连通块是二分图, 另一个连通块不是二分图, 则它们的乘积恰好是 \(1\) 个二分图.
证明: 为二分图中的点进行黑白染色, 因为非二分图内含有奇环, 对于在非二分图上的棋子, 可以在奇环中绕一圈, 而在二分图上的棋子所在点的颜色就会改变. 同样的, 这些点也是互相连通的. 同样因为二分图中的棋子要回到初始点必然要走偶数步, 所以也不存在奇环, 是二分图.
如果两个连通块都不是二分图, 则它们的乘积恰好是 \(1\) 个非二分图.
证明: 同样的, 其中一个棋子在奇环中绕一圈, 另一个棋子一直在一条边上往返, 则可以让另一个棋子移动到边的另一端, 所以点都是连通的. 两个棋子在奇环上绕两环长乘积步, 则就是走了奇数步回到初始位置, 不是二分图.
更一般地, 我们总结两张图乘积的规律:
对于有 \(n\) 个点的图 \(G_1\), 假设其中有 \(a\) 个孤立点,\(b\) 个非孤立点二分图连通块,\(c\) 个非二分图连通块, 我们把这些信息记做 \(\begin{bmatrix}n\\a\\b\\c\end{bmatrix}\).
假设第二张图 \(G_2\) 的信息为 \(\begin{bmatrix}m\\d\\e\\f\end{bmatrix}\). 则可以如下总结两张图的乘积 \(H\) 的规律:
\(H\) 中的点数显然为 \(nm\), 孤立点数为 \(am + nd - ad\), 非孤立点二分图连通块数为 \(2be + bf + ce\), 非二分图连通块数为 \(cf\).
则有图信息之间的乘积公式: \(\begin{bmatrix}n\\a\\b\\c\end{bmatrix}\cdot\begin{bmatrix}m\\d\\e\\f\end{bmatrix}=\begin{bmatrix}nm\\am+nd-ad\\2be+bf+ce\\cf\end{bmatrix}\).
不难发现信息乘积的单位元为 \(\begin{bmatrix}1\\0\\0\\1\end{bmatrix}\), 只要计算出每个 \(k_i\) 的信息之和, 再依次乘起来即可得到图的总乘积 \(H\) 的信息.
接下来考虑计算点数为 \(k_i\) 的所有有标号无向图的信息之和, 也即需要计算这些图中的孤立点总数, 非孤立点二分图连通块总数, 非二分图连通块总数. 请看下列生成函数推导:
\[\begin{aligned} \hat{G}_{\text{arbitrary}} &= \sum_{i = 0}^{\infty} 2^{\binom{i}{2}} \frac{z^i}{i!} & : & [1, 1, 2, 8, 64, 1024, \ldots] \\ \hat{G}_{\text{connected}} &= \ln \hat{G}_{\text{arbitrary}} & : & [0, 1, 1, 4, 38, 728, \ldots] \\ \hat{C}_{\text{connected}} &= \hat{G}_{\text{connected}} \hat{G}_{\text{arbitrary}} & : & [0, 1, 3, 13, 98, 1398, \ldots]\\ \hat{C}_{\text{isolated}} &= z \, \hat{G}_{\text{arbitrary}} & : & [0, 1, 2, 6, 32, 320, \ldots] \\ \hat{G}_{\text{colored bipartite}} &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \binom{i + j}{i} 2^{ij} \frac{z^{(i + j)}}{(i + j)!} & & \\ &= \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} \frac{2^{-\binom{i}{2}}}{i!} \frac{2^{-\binom{j}{2}}}{j!} 2^{\binom{i + j}{2}} z^{(i + j)} & & \\ &= \sum_{n = 0}^{\infty} 2^{\binom{n}{2}} [z^n] {\left( \sum_{i = 0}^{\infty} 2^{-\binom{i}{2}} \frac{z^i}{i!} \right)}^2 & : & [1, 2, 6, 26, 162, 1442, \ldots] \\ \hat{G}_{\text{con-bipartite(not isolated)}} &= \frac{\ln \hat{G}_{\text{colored bipartite}}}{2} - z & : & [0, 0, 1, 3, 19, 195, \ldots] \\ \hat{C}_{\text{con-bipartite(not isolated)}} &= \hat{G}_{\text{con-bipartite(not isolated)}} \hat{G}_{\text{arbitrary}} & : & [0, 0, 1, 6, 43, 430, \ldots] \\ \hat{C}_{\text{connected, not bipartite}} &= \hat{C}_{\text{connected}} - \hat{C}_{\text{isolated}} - \hat{C}_{\text{con-bipartite(not isolated)}} & : & [0, 0, 0, 1, 23, 648, \ldots] \end{aligned}\]
其中:
\(\hat{G}_{\text{arbitrary}}\) 表示 \(n\) 个点的有标号无向图总数的 \(\mathbf{EGF}\);
\(\hat{G}_{\text{connected}}\) 表示 \(n\) 个点的有标号连通无向图总数的 \(\mathbf{EGF}\);
\(\hat{C}_{\text{connected}}\) 表示所有 \(n\) 个点的有标号无向图中的连通块数量总和的 \(\mathbf{EGF}\);
\(\hat{C}_{\text{isolated}}\) 表示所有 \(n\) 个点的有标号无向图中的孤立点数总和的 \(\mathbf{EGF}\);
\(\hat{G}_{\text{colored bipartite}}\) 表示 \(n\) 个点的点二染色的有标号无向二分图总数的 \(\mathbf{EGF}\), 求它的技巧是利用 \(\displaystyle \binom{i + j}{2} = \binom{i}{2} + \binom{j}{2} + ij\) 分离枚举变量 \(i, j\) 使其相互独立;
\(\hat{G}_{\text{con-bipartite(not isolated)}}\) 表示 \(n\) 个点的非孤立点有标号连通无向二分图总数的 \(\mathbf{EGF}\), 因为连通二分图恰好有两种染色方案, 所以将 \(\hat{G}_{\text{colored bipartite}}\) 取对数后再除以 \(2\) 就得到了连通二分图的 \(\mathbf{EGF}\), 再减去 \(z\) 是为了去除孤立点的情况;
\(\hat{C}_{\text{con-bipartite(not isolated)}}\) 表示所有 \(n\) 个点的有标号无向图中的非孤立点二分图连通块数量总和的 \(\mathbf{EGF}\);
\(\hat{C}_{\text{connected, not bipartite}}\) 表示所有 \(n\) 个点的有标号无向图中的非二分图连通块数量总和的 \(\mathbf{EGF}\).
按照生成函数计算即可.
下面是代码, 时间复杂度为 \(\mathcal O (n + \max k_i \log \max k_i)\):
- #include <cstdio>
- #include <algorithm>
- typedef long long LL;
- const int Mod = 998244353, Inv2 = (Mod + 1) / 2;
- const int G = 3, iG = 332748118;
- const int MS = 1 <<18;
- inline int qPow(int b, int e) {
- int a = 1;
- for (; e; e>>= 1, b = (LL)b * b % Mod)
- if (e & 1) a = (LL)a * b % Mod;
- return a;
- }
- inline int gInv(int b) { return qPow(b, Mod - 2); }
- int Inv[MS], Fac[MS], iFac[MS];
- inline void Init(int N) {
- Fac[0] = 1;
- for (int i = 1; i <N; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
- iFac[N - 1] = gInv(Fac[N - 1]);
- for (int i = N - 1; i>= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
- for (int i = 1; i <N; ++i) Inv[i] = (LL)Fac[i - 1] * iFac[i] % Mod;
- }
- inline int Binom(int N, int M) {
- if (M < 0 || M> N) return 0;
- return (LL)Fac[N] * iFac[M] % Mod * iFac[N - M] % Mod;
- }
- int Sz, InvSz, R[MS];
- inline int getB(int N) { int Bt = 0; while (1 <<Bt < N) ++Bt; return Bt; }
- inline void InitFNTT(int N) {
- int Bt = getB(N);
- if (Sz == (1 << Bt)) return ;
- Sz = 1 << Bt, InvSz = Mod - (Mod - 1) / Sz;
- for (int i = 1; i < Sz; ++i) R[i] = R[i>> 1]>> 1 | (i & 1) <<(Bt - 1);
- }
- inline void FNTT(int *A, int Ty) {
- for (int i = 0; i < Sz; ++i) if (R[i] < i) std::swap(A[R[i]], A[i]);
- for (int j = 1, j2 = 2; j < Sz; j <<= 1, j2 <<= 1) {
- int wn = qPow(~Ty ? G : iG, (Mod - 1) / j2), w, X, Y;
- for (int i = 0, k; i < Sz; i += j2) {
- for (k = 0, w = 1; k < j; ++k, w = (LL)w * wn % Mod) {
- X = A[i + k], Y = (LL)w * A[i + j + k] % Mod;
- A[i + k] -= (A[i + k] = X + Y)>= Mod ? Mod : 0;
- A[i + j + k] += (A[i + j + k] = X - Y) < 0 ? Mod : 0;
- }
- }
- }
- if (!~Ty) for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * InvSz % Mod;
- }
- inline void PolyConv(int *_A, int N, int *_B, int M, int *_C, int tN = -1) {
- if (tN == -1) tN = N + M - 1;
- static int A[MS], B[MS];
- InitFNTT(N + M - 1);
- for (int i = 0; i < N; ++i) A[i] = _A[i];
- for (int i = N; i < Sz; ++i) A[i] = 0;
- for (int i = 0; i < M; ++i) B[i] = _B[i];
- for (int i = M; i < Sz; ++i) B[i] = 0;
- FNTT(A, 1), FNTT(B, 1);
- for (int i = 0; i < Sz; ++i) A[i] = (LL)A[i] * B[i] % Mod;
- FNTT(A, -1);
- for (int i = 0; i < tN; ++i) _C[i] = A[i];
- }
- inline void PolyInv(int *_A, int N, int *_B) {
- static int A[MS], B[MS], tA[MS], tB[MS];
- for (int i = 0; i < N; ++i) A[i] = _A[i];
- for (int i = N, Bt = getB(N); i < 1 << Bt; ++i) A[i] = 0;
- B[0] = gInv(A[0]);
- for (int L = 1; L < N; L <<= 1) {
- int L2 = L << 1, L4 = L << 2;
- InitFNTT(L4);
- for (int i = 0; i < L2; ++i) tA[i] = A[i];
- for (int i = L2; i < Sz; ++i) tA[i] = 0;
- for (int i = 0; i < L; ++i) tB[i] = B[i];
- for (int i = L; i < Sz; ++i) tB[i] = 0;
- FNTT(tA, 1), FNTT(tB, 1);
- for (int i = 0; i < Sz; ++i) tB[i] = tB[i] * (2 - (LL)tA[i] * tB[i] % Mod + Mod) % Mod;
- FNTT(tB, -1);
- for (int i = 0; i < L2; ++i) B[i] = tB[i];
- }
- for (int i = 0; i < N; ++i) _B[i] = B[i];
- }
- inline void PolyLn(int *_A, int N, int *_B) {
- static int tA[MS], tB[MS];
- for (int i = 1; i < N; ++i) tA[i - 1] = (LL)_A[i] * i % Mod;
- PolyInv(_A, N - 1, tB);
- InitFNTT(N + N - 3);
- for (int i = N - 1; i < Sz; ++i) tA[i] = 0;
- for (int i = N - 1; i < Sz; ++i) tB[i] = 0;
- FNTT(tA, 1), FNTT(tB, 1);
- for (int i = 0; i < Sz; ++i) tA[i] = (LL)tA[i] * tB[i] % Mod;
- FNTT(tA, -1);
- _B[0] = 0;
- for (int i = 1; i < N; ++i) _B[i] = (LL)tA[i - 1] * Inv[i] % Mod;
- }
- const int MN = 100005;
- inline void Merge(int *A, int *B) {
- static int C[4];
- C[0] = (LL)A[0] * B[0] % Mod;
- C[1] = ((LL)A[1] * B[0] + (LL)A[0] * B[1] - (LL)A[1] * B[1]) % Mod;
- if (C[1] < 0) C[1] += Mod;
- C[2] = (2ll * A[2] * B[2] + (LL)A[2] * B[3] + (LL)A[3] * B[2]) % Mod;
- C[3] = (LL)A[3] * B[3] % Mod;
- A[0] = C[0], A[1] = C[1], A[2] = C[2], A[3] = C[3];
- }
- int N, K[MN], MaxK;
- int A1[MS], A2[MS], A3[MS], A4[MS], A5[MS], A6[MS], A7[MS], A8[MS];
- int C0[MS], C1[MS], C2[MS], C3[MS];
- int main() {
- scanf("%d", &N);
- for (int i = 1; i <= N; ++i) {
- scanf("%d", &K[i]);
- MaxK = std::max(MaxK, K[i]);
- }
- Init(MaxK + 1);
- for (int i = 0; i <= MaxK; ++i) A1[i] = (LL)qPow(2, (LL)i * (i - 1) / 2 % (Mod - 1)) * iFac[i] % Mod;
- PolyLn(A1, MaxK + 1, A2);
- PolyConv(A2, MaxK + 1, A1, MaxK + 1, A3, MaxK + 1);
- for (int i = 1; i <= MaxK; ++i) A4[i] = A1[i - 1];
- for (int i = 0; i <= MaxK; ++i) A5[i] = (LL)qPow(Inv2, (LL)i * (i - 1) / 2 % (Mod - 1)) * iFac[i] % Mod;
- PolyConv(A5, MaxK + 1, A5, MaxK + 1, A5, MaxK + 1);
- for (int i = 0; i <= MaxK; ++i) A5[i] = (LL)A5[i] * qPow(2, (LL)i * (i - 1) / 2 % (Mod - 1)) % Mod;
- PolyLn(A5, MaxK + 1, A6);
- for (int i = 0; i <= MaxK; ++i) A6[i] = (LL)A6[i] * Inv2 % Mod;
- --A6[1];
- PolyConv(A6, MaxK + 1, A1, MaxK + 1, A7, MaxK + 1);
- for (int i = 0; i <= MaxK; ++i) A8[i] = ((LL)A3[i] - A4[i] - A7[i] + Mod * 2) % Mod;
- for (int i = 0; i <= MaxK; ++i) {
- C0[i] = (LL)i * qPow(2, (LL)i * (i - 1) / 2 % (Mod - 1)) % Mod;
- C1[i] = (LL)A4[i] * Fac[i] % Mod;
- C2[i] = (LL)A7[i] * Fac[i] % Mod;
- C3[i] = (LL)A8[i] * Fac[i] % Mod;
- }
- int Ans[4] = {1, 0, 0, 1};
- for (int i = 1; i <= N; ++i) {
- static int Now[4];
- Now[0] = C0[K[i]], Now[1] = C1[K[i]],
- Now[2] = C2[K[i]], Now[3] = C3[K[i]];
- Merge(Ans, Now);
- }
- printf("%lld\n", ((LL)Ans[1] + Ans[2] + Ans[3]) % Mod);
- return 0;
- }
E. 新年的邀请函 http://uoj.ac/contest/50/problem/499
咕.
来源: http://www.bubuko.com/infodetail-3393669.html