M_sea 的博客 - 多项式运算
type: channel
link: https://m-sea-blog.com/tag/多项式运算/
items: 洛谷5206 [WC2019]数树
items: 洛谷3711 仓鼠的数学题
items: 洛谷6597 烯烃计数
items: LOJ6538 烷基计数 加强版 加强版
items: BZOJ3684 大朋友和多叉树
items: 球与盒子问题学习笔记
items: UOJ551 【UNR #4】校园闲逛
items: 洛谷5296 [北京省选集训2019]生成树计数
items: 洛谷4705 玩游戏
items: 多项式全家桶重新学习笔记

洛谷5206 [WC2019]数树
type: item
date: 2021-02-24T07:04:00+00:00
description: Luogu LOJ orz laofu！!1 分析 $op = 0$ 只需要统计两棵树有多少条重边即可。假设有 $c$ 条，答案即为 $y^{n - c}$。 $op = 1$ 先特判掉 $y = 1$ 的情况，答案为 $n^{n - 2}$。 我们要求的是 $$ \sum_{T_2} y^{n - |T_1 \cap T_2|} $$ 交集不好处理，我们考虑这样一个式子 $$ f(S) = \sum_{T \subseteq S} \sum_{P \subseteq T} (-1)^{|T| - |P|} f(P) \tag{1} \label{eq1} $$ [collapse title="证明（可能是伪的）" status="false"] 规定 $0 ^ 0 = 1$，可以证明在下面的推导中这是成立的。 $$ \begin{align} \text{右边} = & \sum_{P \subseteq S} f(P) \sum_{j = 0}^{|S| - |P|} (-1)^j {|S| - |P| \choose j} \\ = & \sum_{P \subseteq S} f(P) (1 - 1)^{|S| - |P|} \\ = & f(S) = \text{左边} \end{align} $$ [/collapse] 把 $\eqref{eq1}$ 套进去得到 $$ \sum_{T_2} \sum_{S \subseteq T_1 \cap T_2} \sum_{T \subseteq S} (-1) ^ {|S| - |T|} y^{n - |T|} $$ 设 $g(S)$ 为包含 $S$ 中边的生成树个数，上式可以变为 $$ \begin{align} & \sum_{S \subseteq T_1} \left(\sum_{T \subseteq S} (-1)^{|S| - |T|} y^{n - |T|}\right) g(S) \\ = & \sum_{S \subseteq T_1} y^{n - |S|} \left(\sum_{T \subseteq S} (-y)^{n - |T|}\right) g(S) \\ = & \sum_{S \subseteq T_1} y^{n - |S|} \left(\sum_{i = 0}^{|S|} {|S| \choose i} (-y)^{n - i}\right) g(S) \\ = & \sum_{S \subseteq T_1} y^{n - |S|} (1 - y)^{|S|} g(S) \\ \end{align} $$ 考虑 $g(S)$ 等于什么。我们把 $S$ 中的边加入，那么原图会构成 $k$ 个大小为 $a_1, a_2, \cdots, a_k$ 的连通块，将它们连成一棵树的方案数为 $$ g(S) = n^{k - 2} \prod_{i = 1}^k a_i $$ [collapse title="证明" status="false"] link [/collapse] 于是上式变为 $$ \begin{align} & \sum_{S \subseteq T_1} y^k (1 - y)^{n - k} n^{k - 2} \prod_{i = 1}^k a_i \\ = & \frac{(1 - y)^n}{n^2} \sum_{S \subseteq T_1} \left(\frac{ny}{1 - y}\right)^k \prod_{i = 1}^k a_i \\ = & \frac{(1 - y)^n}{n^2} \sum_{S \subseteq T_1} \prod_{i = 1}^k \frac{ny}{1 - y} a_i\\ \end{align} $$ 不妨设 $k = \frac{ny}{1 - y}$，上式的实际意义相当于每个大小为 $a$ 的连通块产生 $ka$ 的乘积贡献。 这样子就可以想到一个 DP：设 $f_{i, j}$ 表示以 $i$ 为根的子树、$i$ 所在的连通块大小为 $j$ 的答案，转移为树形背包。然而这样子是 $\mathcal{O}(n^2)$ 的。 考虑把 $a_i$ 写成 $a_i \choose 1$，相当于在每个连通块内选一个点产生 $ka_i$ 的乘积贡献。这样子就有一个更优的 DP：设 $f_{i, 0/1}$ 表示以 $i$ 为根的子树、$i$ 所在连通块是否已经选了一个点产生贡献，转移讨论一下即可。这样子即可做到 $\mathcal{O}(n)$。 $op = 2$ 先判掉 $y = 1$ 的情况，答案为 $n^{2(n - 2)}$。 我们要求的是 $…

洛谷3711 仓鼠的数学题
type: item
date: 2021-02-22T07:09:42+00:00
description: Luogu 分析 为了方便我们先令 $y$ 等于 $x + 1$，则 $S_k(x) = \sum_{i = 0}^{y - 1} i ^ k$。 根据伯努利数的结论有 $$ S_k(y) = \frac{1}{k + 1} \sum_{i = 0}^k {k + 1 \choose i} B_i y^{k + 1 - i} $$ 则答案为 $$ \sum_{k = 0}^n \frac{a_k}{k + 1} \sum_{i = 0}^k {k + 1 \choose i} B_i y ^ {k + 1 - i} $$ 稍作变形得到 $$ \sum_{k = 0}^n \frac{a_k}{k + 1} \sum_{i = 0}^k {k + 1 \choose i + 1} B_{k - i} y ^ {i + 1} $$ 交换求和号并拆掉组合数 $$ \sum_{i = 0}^k \frac{y ^ {i + 1}}{(i + 1)!} \sum_{k = i}^n a_k k! \frac{B_{k - i}}{(k - i)!} $$ 后面是差卷积的形式，翻转后一遍 NTT 即可。 然而 $y = x + 1$，考虑把求出的多项式改写为关于 $x$ 的形式。这相当于已知 $\sum_{i \geq 0} f_i x ^ i$，求 $\sum_{i \geq 0} f_i (x + 1) ^ i$。 用二项式定理拆开 $$ \sum_{i = 0}^{n + 1} f_i \sum_{j = 0}^i {i \choose j} x^j $$ 交换求和号并拆掉组合数 $$ \sum_{j = 0}^{n + 1} \frac{x ^ j}{j!} \sum_{i = j}^n i! f_i \frac{1}{(i - j)!} $$ 后面同样是差卷积的形式，翻转后一遍 NTT 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define debug(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long ll; int read() { int X = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar(); return X * w; } const int N = 524288 + 10; const int mod = 998244353; int qpow(int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) c = 1ll * c * a % mod; return c; } int r[N]; void NTT(int *A, int n, int op) { for (int i = 0; i < n; ++i) if (i < r[i]) swap(A[i], A[r[i]]); for (int i = 1; i < n; i <<= 1) { int rot = qpow(op == 1 ? 3 : 332748118, (mod - 1) / (i << 1)); for (int j = 0; j < n; j += i << 1) for (int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % mod) { int x = A[j + k], y = 1ll * w * A[j + k + i] % mod; A[j + k] = (x + y) % mod, A[j + k + i] = (x - y + mod) % mod; } } if (op == -1) { int inv = qpow(n, mod - 2); for (int i = 0; i …

洛谷6597 烯烃计数
type: item
date: 2021-02-15T13:05:00+00:00
description: Luogu 分析 首先求出烷基的 OGF $F(x)$，具体求解过程可以看这里。 考虑一个烯烃断掉双键后会构成一棵根的儿子数 $\leq 2$、其余节点的儿子数 $\leq 3$ 的树，我们考虑求出其 OGF $G(x)$。 根据 Burnside 引理可以得到 $$ G(x) = 1 + x \frac{F(x) ^ 2 + F(x ^ 2)}{2} $$ 然后求出烯烃的 OGF $H(x)$。同样根据 Burnside 引理可以得到 $$ H(x) = \frac{(G(x) - 1) ^ 2 + G(x ^ 2) - 1}{2} $$ 这里减 $1$ 是因为双键两端都必须有碳原子（双键显然不能连在氢原子上）。 依据上式直接计算即可。时间复杂度 $\mathcal{O}(n \log n)$。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define debug(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long ll; int read() { int X = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar(); return X * w; } const int N = 262144 + 10; const int mod = 998244353, inv2 = 499122177; int qpow(int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) c = 1ll * c * a % mod; return c; } namespace Poly { int r[N]; void NTT(int *A, int n, int op) { for (int i = 0; i < n; ++i) if (i < r[i]) swap(A[i], A[r[i]]); for (int i = 1; i < n; i <<= 1) { int rot = qpow(op == 1 ? 3 : 332748118, (mod - 1) / (i << 1)); for (int j = 0; j < n; j += i << 1) for (int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % mod) { int x = A[j + k], y = 1ll * w * A[j + k + i] % mod; A[j + k] = (x + y) % mod, A[j + k + i] = (x - y + mod) % mod; } } if (op == -1) { int inv = qpow(n, mod - 2); for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod; } } int NTT_init(int n) { int lim = 1, l = 0; for (; lim < n; lim <<= 1, ++l); for (int i = 0; i < lim; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); return lim; } void PolyInv(int *F, int *G, int n) { static int A[N], B[N]; if (n == 1) { G[0] = qpow(F[0], mod - 2); return; } PolyInv(F, G, n >> 1); for (int i = 0; i < n; ++i) A[i] = F[i], B[i] = G[i]; int lim = NTT_init(…

LOJ6538 烷基计数 加强版 加强版
type: item
date: 2021-02-15T12:41:23+00:00
description: LOJ 分析 要求的就是每个节点的儿子数都不超过 $3$ 的无标号有根树数。 设其 OGF 为 $F(x)$，考虑列出一个关于 $F(x)$ 的方程。 不妨规定 $[x^0]F(x) = 1$，那么可以看成每个节点的儿子数都恰好为 $3$。 直接得出 $F(x) = 1 + F(x) ^ 3$ 显然是错误的，因为我们同构的情况被重复计算了。 因此可以考虑 Burnside 引理。对于 $(1, 2, 3)$，所有情况都是不动点；对于 $(1, 3, 2)$、$(3, 2, 1)$、$(2, 1, 3)$，在置换中成环的两棵子树同构的情况是不动点；对于 $(3, 1, 2)$、$(2, 3, 1)$，三棵子树都同构的情况是不动点。 这样子我们就可以列出方程 $$ F(x) = 1 + x \frac{F(x) ^ 3 + 3 F(x ^ 2) F(x) + 2 F(x ^ 3)}{6} $$ 考虑使用牛顿迭代解出 $F(x)$。设 $G(F(x)) = 1 + x \frac{F(x) ^ 3 + 3 F(x ^ 2) F(x) + 2 F(x ^ 3)}{6} - F(x) = 0$。 假设当前已知 $F_0(x) = F(x) \bmod x ^ {\frac{n}{2}}$，要求 $F(x) \bmod x ^ n$。那么事实上 $F(x ^ 2) \bmod{x ^ n}$ 和 $F(x ^ 3) \bmod x ^ n$ 已知，因此可以将其看作常量 $A(x)$ 和 $B(x)$。这样子有 $$ G'(F(x)) = x \frac{F(x) ^ 2 + 3 A(x)}{6} - 1 $$ 套牛顿迭代的式子 $$ F(x) = F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))} $$ 这样子就可以求出 $F(x)$ 了。时间复杂度 $\mathcal{O}(n\log n)$。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define debug(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long ll; int read() { int X = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar(); return X * w; } const int N = 262144 + 10; const int mod = 998244353, inv2 = 499122177; int qpow(int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) c = 1ll * c * a % mod; return c; } namespace Poly { int r[N]; void NTT(int *A, int n, int op) { for (int i = 0; i < n; ++i) if (i < r[i]) swap(A[i], A[r[i]]); for (int i = 1; i < n; i <<= 1) { int rot = qpow(op == 1 ? 3 : 332748118, (mod - 1) / (i << 1)); for (int j = 0; j < n; j += i << 1) for (int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % mod) { int x = A[j + k], y = 1ll * w * A[j + k + i] % mod; A[j + k] = (x + y) % mod, A[j + k + i] = (x - y + mod) % mod; } } if (op == -1) { in…

BZOJ3684 大朋友和多叉树
type: item
date: 2021-02-09T07:51:00+00:00
description: darkbzoj 分析 设答案的 OGF 为 $F(x)$，则有 $$ F(x) = x + \sum_{i \in D} F(x) ^i $$ 即 $$ x = F(x) - \sum_{i \in D} F(x)^i $$ 令 $G(x) = F^{-1}(x)$，可知 $$ G(x) = x - \sum_{i \in D} x^i $$ 由拉格朗日反演可得 $$ [x^n]F(x) = \frac{1}{n} [x^{n - 1}] \left(\frac{x}{G(x)}\right) ^ n $$ 注意到 $[x^0] G(x) = 0$，所以我们把上下同时除以 $x$，上式变为 $$ [x^n]F(x) = \frac{1}{n} [x^{n - 1}] \left(\frac{1}{\frac{G(x)}{x}}\right) ^ n $$ 多项式求逆 + 多项式快速幂计算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define debug(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long ll; int read() { int X = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar(); return X * w; } const int N = 262144 + 10; const int mod = 950009857; int qpow(int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) c = 1ll * c * a % mod; return c; } int r[N]; void NTT(int *A, int n, int op) { for (int i = 0; i < n; ++i) if (i < r[i]) swap(A[i], A[r[i]]); for (int i = 1; i < n; i <<= 1) { int rot = qpow(op == 1 ? 7 : 135715694, (mod - 1) / (i << 1)); for (int j = 0; j < n; j += i << 1) for (int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % mod) { int x = A[j + k], y = 1ll * w * A[j + k + i] % mod; A[j + k] = (x + y) % mod, A[j + k + i] = (x - y + mod) % mod; } } if (op == -1) { int inv = qpow(n, mod - 2); for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod; } } int NTT_init(int n) { int lim = 1, l = 0; for (; lim < n; lim <<= 1, ++l); for (int i = 0; i < lim; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); return lim; } void PolyInv(int *F, int *G, int n) { static int A[N], B[N]; if (n == 1) { G[0] = qpow(F[0], mod - 2); return; } PolyInv(F, G, n >> 1); for (int i = 0; i < n; ++i) A[i] = F[i], B[i] = G[i]; int …

球与盒子问题学习笔记
type: item
date: 2021-02-07T03:25:00+00:00
description: 球与盒子问题大杂烩 下面我们对这 $12$ 个问题简略分析。 I 球之间互不相同，盒子之间互不相同。 每个球都可以任意选择一个盒子，答案为 $m^n$。 II 球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。 每个球选择一个盒子，已经被选择过的盒子不能再被选择，答案为 $m^{\underline{n}}$。 III 球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。 考虑容斥，枚举空盒子的个数，不难得到答案为 $$ \sum _ {i = 0} ^ m (-1) ^ i {m \choose i} (m - i) ^ n $$ IV 球之间互不相同，盒子全部相同。 枚举非空盒子的个数，不难得到答案为 $$ \sum_{i = 0} ^ m \begin{Bmatrix} n \\ i \end{Bmatrix} $$ 使用 第二类斯特林数·行 的方法计算即可。具体可以看这里。 V 球之间互不相同，盒子全部相同，每个盒子至多装一个球。 答案为 $[n \leq m]$。 VI 球之间互不相同，盒子全部相同，每个盒子至少装一个球。 答案为 $\begin{Bmatrix} n \\ m \end{Bmatrix}$。 VII 球全部相同，盒子之间互不相同。 使用插板法计算，答案为 ${n + m - 1 \choose m - 1}$。 VIII 球全部相同，盒子之间互不相同，每个盒子至多装一个球。 相当于选 $n$ 个盒子放球，答案为 ${m \choose n}$。 IX 球全部相同，盒子之间互不相同，每个盒子至少装一个球。 使用插板法计算，答案为 ${n - 1 \choose m - 1}$。 X 球全部相同，盒子全部相同。 定义划分数 $p_{n, m}$ 为 $n$ 划分为 $m$ 个自然数的方案数。有一个很经典的转移 $$ p_{n, m} = p_{n, m - 1} + p_{n - m, m} $$ 意思是：加一个 $0$，或者把所有数 $+1$。 设生成函数 $F_m(x) = \sum_{i \geq 0} p_{i, m} x ^ i$，那么有 $$ F_m(x) = F_{m-1}(x) (1 + x ^ m + x ^ {2m} + \cdots) = \frac{F_{m - 1}(x)}{1 - x^m} $$ 从而 $$ F_m(x) = \prod_{i = 1} ^ m \frac{1}{1 - x^i} $$ 考虑取对数。通过一些推导可以知道 $$ \ln \frac{1}{1 - x^i} = \sum_{j\geq 1} \frac{x^{ij}}{j} $$ 这样子就可以 $\mathcal{O}(m\ln m)$ 求出 $\ln F_m(x)$，再多项式 exp 回去即可。 XI 球全部相同，盒子全部相同，每个盒子至多装一个球。 答案为 $[n \leq m]$。 XII 球全部相同，盒子全部相同，每个盒子至少装一个球。 相当于先往每个盒子里装一个球，答案为 $p_{n - m, m}$。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define debug(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long ll; int read() { int X = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar(); return X * w; } const int N = 524288 + 10; const int mod = 998244353; int qpow(int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) c = 1ll * c * a % mod; retur…

UOJ551 【UNR #4】校园闲逛
type: item
date: 2021-01-30T13:39:00+00:00
description: UOJ 分析 设 $f_{i ,j, w}$ 为从 $i$ 走到 $j$、权值和为 $w$ 的方案数，$g_{i, j, w}$ 表示连接 $i,j$ 的权值为 $k$ 的边数。 那么有 $$ f_{i, j, w} = \sum_{k = 1}^n \sum_{v} f_{i, k, v} \times g_{k, j, w - v} + [i = j \land w = 0] $$ 后面那个中括号表示不走的情况。 设 $F_{i,j}(x) = \sum_{k\geq 0} f_{i,j,k} x^k$，$G_{i,j}(x) = \sum_{k\geq 0} g_{i, j, k} x^k$，并设 $F,G$ 表示这两个生成函数构成的矩阵，则有 $$ F = F\times G + I $$ 即 $$ F = \frac{I}{I - G} $$ 可以证明 $I-G$ 一定是可逆的。于是我们只需要求一个每个元素都是一个多项式的矩阵的逆，和普通矩阵求逆类似地做即可。 然而这题还卡常，需要精细地实现来减少 NTT 的次数，最好把预处理原根、取模优化、寻址优化什么的都加上去。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define debug(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long ll; int read() { int X = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar(); return X * w; } const int N = 8 + 5, W = 131072 + 10; const int mod = 998244353; int upd(const int &x) { return x + (x >> 31 & mod); } int qpow(int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) c = 1ll * c * a % mod; return c; } int r[W], w[W], ow[2][W], Lim; void NTT(int *A, int n, int op) { for (int i = 0; i < n; ++i) if (i < r[i]) swap(A[i], A[r[i]]); for (int i = 1; i < n; i <<= 1) { for (int j = 0, k = 0; j < i; ++j, k += Lim / i) w[j] = ow[op < 0][k]; for (int j = 0; j < n; j += i << 1) for (int k = 0; k < i; ++k) { int x = A[j + k], y = 1ll * w[k] * A[j + k + i] % mod; A[j + k] = upd(x + y - mod), A[j + k + i] = upd(x - y); } } if (op == -1) { int inv = qpow(n, mod - 2); for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod; } } int NTT_init(int n) { int lim = 1, l = 0; for (; lim < n; lim <<= 1, ++l); for (int i = 0; i < lim; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); return lim; } void PolyInv(int *F, int *G, int n) { stati…

洛谷5296 [北京省选集训2019]生成树计数
type: item
date: 2020-10-27T13:25:49+00:00
description: Luogu 分析 根据二项式定理有 $$ (a_1+a_2+\cdots+a_n)^k=k![x^k]\prod e^{a_ix} $$ 所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。 因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout) #define debug(...) fprintf(stderr,__VA_ARGS__) using namespace std; typedef long long ll; int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=30+5; const int mod=998244353; int qpow(int a,int b) { int c=1; for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod; return c; } int n,k,fac[N],ifac[N]; void init(int n) { fac[0]=1; for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod; ifac[n]=qpow(fac[n],mod-2); for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod; } struct poly { int a[N]; poly() { memset(a,0,sizeof(a)); } poly(int w) { for (int i=0,pw=1;i<=k;++i,pw=1ll*pw*w%mod) a[i]=1ll*pw*ifac[i]%mod; } int& operator [](int i) { return a[i]; } }; poly operator +(poly a,poly b) { poly c; for (int i=0;i<=k;++i) c[i]=(a[i]+b[i])%mod; return c; } poly operator -(poly a,poly b) { poly c; for (int i=0;i<=k;++i) c[i]=(a[i]-b[i]+mod)%mod; return c; } poly operator *(poly a,poly b) { poly c; for (int i=0;i<=k;++i) for (int j=0;j<=i;++j) c[i]=(c[i]+1ll*a[j]*b[i-j])%mod; return c; } poly polyinv(poly a) { poly b; b[0]=qpow(a[0],mod-2); for (int i=1;i<=k;++i) { int s=0; for (int j=0;j<i;++j) s=(s+1ll*b[j]*a[i-j])%mod; b[i]=1ll*b[0]*(mod-s)%mod; } return b; } poly C[N][N]; poly det(int n) { poly ans(0); for (int i=1;i<=n;++i) { ans=ans*C[i][i]; poly inv=polyinv(C[i][i]); for (int j=i+1;j<=n;++j) { poly t=C[j][i]*inv; for (int k=i;k<=n;++k) C[j][k]=C[j][k]-t*C[i][k]; } } return ans; } int main() { n=read(),k=read(); init(k); for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) { int w=read(); if (i>=j) continue; …

洛谷4705 玩游戏
type: item
date: 2020-10-26T01:14:05+00:00
description: Luogu 分析 答案显然是 $$ \frac{\sum_{i=1}^n\sum_{j=1}^m(a_i+b_j)^k}{nm} $$ 我们不管分母，只看分子。用二项式定理拆开得到 $$ \sum_{i=1}^n\sum_{j=1}^m\sum_{r=0}^k{k\choose r}a_i\!^rb_j\!^{k-r} $$ 稍微换一下形式得到 $$ \sum_{r=0}^k{k\choose r}\left(\sum_{i=1}^na_i\!^r\right)\left(\sum_{i=1}^mb_i\!^{k-r}\right) $$ 如果我们能够对每个 $r$ 快速求出 $\sum_{i=1}^n a_i\!^r$，那么就可以直接卷了。 这是一个经典问题（鸡贼说叫“等幂和”）。我们相当于要求生成函数 $$ A(x)=\sum_{r\geq 0}x^r\sum_{i=1}^n a_i\!^r $$ 的前若干项系数。 我们把 $A(x)$ 换一个形式写出来 $$ A(x)=\sum_{i=1}^n\frac{1}{1-a_ix} $$ 根据这类问题的方法，设 $$ G(x)=\sum_{i=1}^n\frac{-a_i}{1-a_ix} $$ 那么有 $$ A(x)=n-xG(x) $$ 考虑怎么算 $G(x)$。注意到 $$ \ln(1-a_ix)'=\frac{-a_i}{1-a_ix} $$ 于是可以想到把 $G(x)$ 化成 $$ G(x)=\sum_{i=1}^n\ln(1-a_ix)' $$ 把 $\sum$ 丢到 $\ln$ 里去得到 $$ G(x)=\ln\left(\prod_{i=1}^n(1-a_ix)\right)' $$ 直接分治把所有 $1-a_ix$ 卷起来，然后多项式 $\ln$ + 多项式求导即可求出 $G(x)$，再推回 $A(x)$ 后卷积即可。 代码 不想写 vector，于是从鱼那里蒯了一个分治 /kel // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout) #define debug(...) fprintf(stderr,__VA_ARGS__) using namespace std; typedef long long ll; int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=400000+10; const int mod=998244353; int qpow(int a,int b) { int c=1; for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod; return c; } int r[N]; void NTT(int *A,int n,int op) { for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (int i=1;i<n;i<<=1) { int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1)); for (int j=0;j<n;j+=i<<1) for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) { int x=A[j+k],y=1ll*w*A[j+k+i]%mod; A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod; } } if (op==-1) { int inv=qpow(n,mod-2); for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod; } } int NTT_init(int n) { int lim=1,l=-1; for (;lim<n;lim<<=1,++l); for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l); return …

多项式全家桶重新学习笔记
type: item
date: 2020-10-20T12:15:00+00:00
description: 为了方便，下文中的多项式长度和 $n$ 均为 $2$ 的幂（多项式除法、三角函数和反三角函数除外），模数均为 $998244353$。 下面所有函数中（除了 NTT_init）传进去的 $n,m$ 都是多项式项数而不是次数。 多项式乘法 这是前置知识，如果不会建议「点开洛谷题面单击右边蓝色按钮题解」。 int r[N]; void NTT(int* A,int n,int op) { for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (int i=1;i<n;i<<=1) { int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1)); for (int j=0;j<n;j+=i<<1) for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) { int x=A[j+k],y=1ll*w*A[j+k+i]%mod; A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod; } } if (op==-1) { int inv=qpow(n,mod-2); for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod; } } int NTT_init(int n) { int lim=1,l=-1; for (;lim<n;lim<<=1,++l); for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l); return lim; } 多项式求导 $$ (x^a)'=ax^{a-1} $$ void getderi(int* F,int* G,int n) { for (int i=1;i<n;++i) G[i-1]=1ll*F[i]*i%mod; G[n-1]=0; } 多项式不定积分 $$ \int x^a\mathrm{d}x=\frac{x^{a+1}}{a+1} $$ void getinte(int* F,int* G,int n) { for (int i=1;i<n;++i) G[i]=1ll*F[i-1]*qpow(i,mod-2)%mod; G[0]=0; } 多项式牛顿迭代 已知 $G(x)$，求 $F(x)$ 满足 $G(F(x))\equiv 0\pmod{x^n}$。 假设我们已经求出了 $F_o(x)$ 满足 $G(F_0(x))\equiv 0\pmod{x^{\frac{n}{2}}}$，将 $G(x)$ 在 $F_0(x)$ 处泰勒展开得到 $$ G(F(x))=\sum_{i=0}^{+\infty}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i $$ 可以发现 $i\geq 2$ 时在模 $x^n$ 意义下都为 $0$，所以 $$ G(F(x))\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\pmod{x^n} $$ 又 $G(F(x))=0$，化简得到 $$ F(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n} $$ 多项式求逆 已知 $F(x)$，求 $G(x)$ 满足 $F(x)G(x)\equiv 1\pmod{x^n}$。 Luogu 假设我们已经求出了 $G_0(x)$ 满足 $F(x)G_0(x)\equiv 1\pmod{x^{\frac{n}{2}}}$，那么 $$ F(x)(G(x)-G_0(x))\equiv 0\pmod{x^\frac{n}{2}} $$ 所以 $$ G(x)-G_0(x)\equiv 0\pmod{x^{\frac{n}{2}}} $$ 平方得到 $$ G(x)^2-2G(x)G_0(x)+G_0(x)^2\equiv 0\pmod{x^n} $$ 乘上 $F(x)$ 即可得到 $$ G(x)\equiv 2G_0(x)-F(x)G_0(x)^2\pmod{x^n} $$ 这样就可以由 $G_0(x)$求出 $G(x)$ 了。 void getinv(int* F,int* G,int n) { static int A[N],B[N]; if (n==1) { G[0]=qpow(F[0],mod-2); return; } getinv(F,G,n>>1); for (int i=0;i<n;++i) A[i]=F[i],B[i]=G[i]; int lim=NTT_init(n<<1); NTT(A,lim,1),NTT(B,lim,1); for (int i=0;i<lim;++i) A[i]=1…