洛谷题目链接
AT原题
考虑构造出来的序列 \(a\) 的特征，因为每次会给 \(a_i\) 加 \(1\)，\(a_j\) 加 \(2\)，所以每次操作后 \(\sum a_i\) 会加上 \(3\)。
所以有\(\sum a_i =3m\) 。
又因为每次操作只给一个数加 \(1\)，所以每次操作要么给序列加入一个奇数，要么使原来的一个奇数变成偶数。
所以序列中的奇数个数设为 \(k\) 的奇偶性与 \(m\) 相同，即 \(k=\sum a_i\%2\)，\(k\equiv m (mod\ 2)\)。
考虑枚举奇数个数 \(k\)，假设这 \(k\) 个数一开始就各加上了 \(1\)，然后把剩下的两次加 \(1\) 当成一次加 \(2\) 来看。
于是便只剩下 \(\frac{3m-k}{2}\) 次加 \(2\) 操作，便变成了把 \(\frac{3m-k}{2}\) 分成 \(n\) 个非负整数。
求把 \(p\) 个数分为 \(n\) 个非负整数的方案，就等于把 \(p+n\) 个数分为 \(n\) 个正整数。
考虑有一个全为 \(1\) 的，长度为 \(p+n\) 的数列，把其分割成 \(n\) 段，即可得到需要的 \(n\) 个正整数。
因为要分成 \(n\) 段，所以割 \(n-1\) 次，方案就是 \(C_{p+n-1}^{n-1}\) 种。
所以答案为 \(\sum_{k\equiv m(mod\ 2)}^{m} C_{n}^{i}\cdot C_{\frac{3m-k}{2}+n-1}^{n-1}\)。
但是这样还是不对，因为题目中说 \(i\ne j\)，所以这个数列里的数不能出现大于 \(2m\) 的数。
但是大于 \(2m\) 的数最多也只有一个，把它减掉 \(2m+1\) 即可转换为把 \(m-1\) 分为 \(n\) 个非负整数。
方案数为 \(C_{n+m-2}^{m}\cdot n\)，减掉它就可以了。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=2e6+9;
int fac[N],inv[N];
int qpow(int a,int k)
{
int now=1;
while(k)
{
if(k&1) now=(now*a)%mod;
a=(a*a)%mod;
k>>=1;
}
return now;
}
int C(int a,int b)
{
if(b>a)
return 0;
return (fac[a]*inv[b]%mod)*inv[a-b]%mod;
}
int n,m,ans;
signed main()
{
fac[0]=1;
for(int i=1;i<N;i++)
{
fac[i]=(fac[i-1]*i)%mod;
}
inv[N-1]=qpow(fac[N-1],mod-2);
for(int i=N-1;i>=1;i--)
inv[i-1]=(inv[i]*i)%mod;
cin>>n>>m;
for(int i=m%2;i<=m;i+=2)
{
ans=(ans+C(n,i)*C((3*m-i)/2+n-1,n-1)%mod)%mod;
}
ans=((ans-n*C(n+m-2,n-1)%mod)%mod+mod)%mod;
cout<<ans;
return 0;
}