ABC276G 题解

· · 题解

传送门： G - Count Sequences

题目大意： 求长度为 n 的整数序列 a_i 的个数，满足：

生成函数入门题，完全不需要考虑组合意义。

首先有一个很明显的 O(nm^2) dp，记 f_{i,j} 为考虑序列前 i 个数，且 a_i=j 时的序列个数，有转移：

f_{i,j} = \begin{cases} 1 &i=1\\ \sum_{ 0 \le k \le j, k \not \equiv j } f_{i-1,k} &i > 1 \end{cases}

可以用前缀和优化到 O(nm)，但很明显不够，考虑设OGF F_i(x) = \sum_{j \ge 0} f_{i,j}x^j，上面的转移式就变成了：

F_i(x) = \begin{cases} \dfrac{1}{1-x} &i=1\\ \dfrac{x^2+x}{1-x^3} F_{i-1}(x) &i > 1 \end{cases}

很明显可以得到 F_i(x) 的封闭形式：

F_i(x) = \dfrac{(x^2+x)^{i-1}}{(1-x)(1-x^3)^{i-1}}

最后的答案是 \sum_{i=0}^m f_{n,i}，那么我们要求的就是：

\begin{aligned} &\sum_{i=0}^m[x^i] F_n(x) \\ = &[x^m]\dfrac{1}{1-x}F_{n}(x)\\ = &[x^m] \dfrac{(x^2+x)^{n-1}}{(1-x)^2(1-x^3)^{n-1}}\\ = &[x^m] \dfrac{x^{n-1}(x+1)^{n-1}}{(1-x)^2(1-x^3)^{n-1}}\\ = &[x^{m-n+1}] \dfrac{(x+1)^{n-1}}{(1-x)^2} \cdot \dfrac{1}{(1-x^3)^{n-1}}\\ \end{aligned}

其中 \dfrac{(x+1)^{n-1}}{(1-x)^2} 就是 (x+1)^{n-1} 的二阶前缀和，而 (x+1)^{n-1},\dfrac{1}{(1-x^3)^{n-1}} 均为经典的关于组合数的生成函数：

\begin{aligned} (x+1)^{n-1} &= \sum_{i \ge 0} \binom{n-1}{i}x^i\\ \dfrac{1}{(1-x^3)^{n-1}} &= \sum_{i \ge 0} \binom{i+n-2}{n-2}(x^3)^i \end{aligned} ~~感觉这个式子找不出什么组合意义。~~ 题外话：使用线性递推可以做到 $O(n \log n \log m)$，$n$ 开到 $10^5$ 级别，此时 $m$ 可以开到 $10^{18}$。 代码： ```cpp #include <bits/stdc++.h> #define lowbit(x) (x & -x) #define pb push_back #define mp make_pair using namespace std; typedef long long ll; const int V = 1e7+5; const int Mod = 998244353; int n, m, ans; ll fac[V], finv[V], F[V]; inline int qpow(int a, int b) { ll base = a, ans = 1; while (b) { if (b & 1) ans = ans * base % Mod; base = base * base % Mod; b >>= 1; } return ans; } inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; } inline ll C(int n, int m) { if (m > n) return 0; return fac[n] * finv[m] % Mod * finv[n - m] % Mod; } int main() { fac[0] = 1; for (int i = 1; i < V; i++) fac[i] = fac[i - 1] * i % Mod; finv[V - 1] = qpow(fac[V - 1], Mod - 2); for (int i = V - 1; i; i--) finv[i - 1] = finv[i] * i % Mod; scanf("%d%d", &n, &m); F[0] = 1; for (int i = 1; i <= m - n + 1; i++) F[i] = (F[i - 1] + C(n - 1, i)) % Mod; for (int i = 1; i <= m - n + 1; i++) F[i] = (F[i - 1] + F[i]) % Mod; for (int i = 0; i <= m - n + 1; i += 3) Add(ans, C(i / 3 + n - 2, n - 2) * F[m - n + 1 - i] % Mod); printf("%d", ans); return 0; } ```