本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-06 10:19:23

传送门： G - Count Sequences

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

• $0 \le a_1 \le a_2 \le \dots \le a_n \le m$.
• $\forall 1 \le i < n,a_i \not \equiv a_{i+1} \pmod{3}$.

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

首先有一个很明显的 $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} $$

$\dfrac{(x+1)^{n-1}}{(1-x)^2},\dfrac{1}{(1-x^3)^{n-1}}$ 的前 $m-n+1$ 项均可在线性时间内算出，同样可在线性时间内算出二者卷积的第 $m-n+1$ 项，总复杂度线性。

感觉这个式子找不出什么组合意义。

题外话：使用线性递推可以做到 $O(n \log n \log m)$，$n$ 开到 $10^5$ 级别，此时 $m$ 可以开到 $10^{18}$。

代码：

#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;
}