Description

给定 $n,m$，求满足以下条件的整数序列 $A=(a_1,a_2,\dots ,a_N)$ 的个数模 $998244353$ 的值。

条件：

• $\forall i\in [1,n):a_i\not\equiv a_{i+1}(\mathrm{mod}3)\wedge a_i\le a_{i+1}$

• $a_i\in [0,m]$

Analysis

首先这道题有一个很套路的 dp 做法：设 $f_{i,j}$ 表示第 $i$ 个数，上一个选的数取模 $3$ 的余数为 $j$ 的方案数。这样转移复杂度是 $O(nm)$ 的。

考虑用组合数学的计算方法优化成线性复杂度。

发现相邻两项不同余 $3$ 其实就相当于相邻两项的差不整除 $3$。

则我们可以用差分数组来改变一下题目的原有条件。

定义：
$$\begin{gathered} \forall i\in [2,n]:d_i=a_i-a_{i-1} \\ {d}_1=a_1 \end{gathered}$$
则题目要求 $\forall i\in [2,n]:d_i\not\equiv 0(\mathrm{mod}3)$。也就是在满足条件的 $A$ 中，$d_i$ 可以被表示为 $3k+1$ 或 $3k+2$ 的形式。

看到这里脑中就应该浮现出隔板法的模型了。题目就又可以转化为：
$$\begin{gathered} 假设\exists a_{n+1}=m \\ \Rightarrow \sum _{i=1}^{n+1}{d}_i=m \\ \Rightarrow 求不定方程x_1+x_2+\cdots +x_{n+1}=m(x_i\in \mathbb{N})的解的组数 \end{gathered}$$
根据隔板法，若不考虑 $d_i$ 的限制，我们可能会立刻想到答案为 $\left(\genfrac{}{}{0ex}{}{m+1}{n}\right)$。

解释也很简单：在我们要把数字 $m$ 分成 $n+1$ 份，就相当于在值域 $[0,m]$ 共 $m+1$ 个数里插 $n$ 个隔板。

但这是不对的。

原因是这道题和常规的隔板不大一样，常规隔板是 $n$ 个元素往 $m$ 个空里放，两个元素不能放到同一个空里。这样答案是 $\left(\genfrac{}{}{0ex}{}{m}{n}\right)$，但这道题两个物品可以放在同一个空里面（因为 $x$ 可以为 $0$）。

我们考虑如何转化，有一个很妙的思路：考虑将等式左边的所有 $x$ 都加上 $1$，这样就能保证所有的 $x\ge 1$。此时原方程变为：$x_1+x_2+\cdots +x_{n+1}=m+n+1$，此时再用正常的隔板法就能求得正确的答案了：$\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$。（上面不是 $m+n+1$ 是因为此时 $x$ 一定不为 $0$，所以答案的值域实际为 $[1,m+n]$）

还有一种更巧妙的解释方式。考虑把隔板也看成是一个物品，那么我们此时就有 $m+n$ 个物品，我们只要选出 $n$ 个隔板所在的位置，就能确定剩下物品的位置。所以选定隔板的方案数就是总的方案数：$\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$，答案一样。但第一个方法是一个通法，适用范围更广。

然后考虑加上不同余 $3$ 的限制。承接上文，所有的 $d_i(1<i<n+1)$ 都可以表示为 $3k+1$ 或 $3k+2$ 的形式。

发现隔板法其实可以转化为一个“分数字”的过程。

所以我们可以枚举有 $x$ 个 $d_i$ 为 $3k+1$，那么就有 $n+1-x$ 个 $3k+2$（因为一共 $n+1$ 个数）。

因为所有的 $d_i$ 都有 $3k$ 这个部分，所以我们先放多出来的 $1$ 和 $2$。这样，摆在我们面前的问题就是：所有的 $d_i$ 初始都是 $0$，我们要把 $x$ 个 $1$ 和 $n+1-x$ 个 $2$ 分给所有的 $d_i$。要注意的是分完之后只有 $d_1$ 和 $d_{n+1}$ 可以是 $0$，剩下的必须是 $1$ 或 $2$。

那么，单独放 $1$ 和 $2$ 的方案数显然就是 $\left(\genfrac{}{}{0ex}{}{n+1}{x}\right)$。（确定了放 $1$ 的个数后 $2$ 的直接就放上去就可以）

因为现在我们不确定 $d_1$ 和 $d_{n+1}$，所以我们可以先枚举 $d_1\in [0,2]$。（$d_{n+1}$ 先不急，后面有妙用）

分完之后，我们要分的数还剩下 $m-d_1-x-2(n+1-x)$（如果剩下的数小于 $0$ 无解），这些数要变成若干个 $3k$ 分给 $n+1$ 个数，其实就是变成若干个 $3$ 分给每个数。（因为我们不关注具体的分数过程，只关心方案数）

我们希望 $m-d_1-x-2(n+1-x)$ 一定是 $3$ 的倍数，这样是符合我们上面的逻辑的。但一切事情都不会进行的那么顺利，假设它不是 $3$ 的倍数，因为我们还没分 $d_{n+1}$，我们就可以利用处于“法外之地”的 $d_{n+1}$ 使它变成 $3$ 的倍数。即 $d_{n+1}$ 的值一定是 $[m-d_1-x-2(n+1-x)]\mathrm{mod}3$。

现在，解决了余数的问题，我们要分的 $3$ 的个数就是 $p=\lfloor \frac{m-d_1-x-2(n+1-x)}{3}\rfloor$ 了。

把这么多个 $3$ 分给 $n$ 个数，根据上面讲的隔板法，方案数即为：$\left(\genfrac{}{}{0ex}{}{p+n}{n}\right)$。

最后的最后，把分 $1,2$ 的方案数和分 $3$ 的方案数乘起来即为答案：$\left(\genfrac{}{}{0ex}{}{n+1}{x}\right)\left(\genfrac{}{}{0ex}{}{p+n}{n}\right)$。

这道题相当于 NOIP T2 的难度，是一道数学推导的好题！关键在于转换差分数组和想到”分数字“这一重要操作。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e7 + 2e6; // C(n+p,n) 中n+p可能大于1e7，要开得大一点
const int mod = 998244353;
typedef long long ll;int fac[maxn], ifac[maxn]; // 阶乘、阶乘逆元（开int数组减小空间）ll Pow(ll x, ll y){ // 快速幂if(y == 0) return 1;if(y == 1) return x % mod;ll sq = Pow(x, y / 2);if(y & 1){return sq * sq % mod * x % mod;}return sq * sq % mod;
}int C(int n, int m){ // C(n,m): n个数里选m个的组合数// C(n,m) = n! / [m! * (n-m)!]return (n < m || m < 0)? 0 : (1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod);
}void pretreatment(){// 求普通阶乘fac[0] = 1;for(int i = 1; i < maxn; i ++) fac[i] = 1LL * fac[i - 1] * i % mod;// 递推求阶乘逆元ifac[maxn - 1] = Pow(fac[maxn - 1], mod - 2);for(int i = maxn - 2; i >= 0; i --) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
}signed main()
{pretreatment();int n, m; cin >> n >> m;ll ans = 0;for(int x = 0; x <= n - 1; x ++){for(int d1 : {0, 1, 2}){int p = (m - d1 - x - 2*(n - 1 - x));if(p < 0) continue;p /= 3; // 细节：先除3有可能让一个负数变成0（例如-2/3=0，所以要先判断再除）ans += 1LL * C(n - 1, x) * C(p + n, n) % mod;ans %= mod;}}cout << ans << '\n';return 0;
}