[AGC036C] GP 2 题解

洛谷题目链接
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;
}