题解：AT_agc036_c [AGC036C] GP 2

include13_fAKe · 2025-11-14 17:44:05 · 题解

本题相当于要对这样的序列进行计数：

• \sum_{i=1}^{n}a_i=3\times m
• \max\left\{ a_i\right \}\le 2\times m
• \sum_{i=1}^{n} a_i\pmod2\le m

看到这种题可以往容斥的角度上面去思考。本题考虑对第二个限制进行容斥。

首先考虑去掉第二个限制。枚举奇数位置的个数 i，数量为 C_n^i。接下来相当于这些位置被填上了 1，n 个位置都再填一个偶数。相当于有 \frac{3\times m-i}{2} 个球要用 n-1 个板隔开。

接下来考虑不满足第二个限制的情况，发现此时必然满足第三个限制。原因留给读者思考。相当于在某一个盒子内放置了 2\times m+1 个球，剩下的隔板。仍然要枚举是拿一个盒子放多了，不过可以简简单单乘以 n 搞定。

设 n,m 同阶，通过线性求逆元可以做到 O(n+\log V)。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
} 
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' '); 
} 
inline void write2(int x){
    write(x),putchar('\n');
}
const int N=5e6+15;
const int mod=998244353;
int jc[N];
int inv[N];
inline int qpow(int x,int y){
    if(y==0)    return 1;
    if(y==1)    return x;
    int ret=qpow(x,y/2);
    ret=ret*ret%mod;
    if(y&1) ret=ret*x%mod;
    return ret;
}
void init(){
    jc[0]=1;
    for(int i=1;i<=5000000;i++){
        jc[i]=jc[i-1]*i%mod; 
    }
    inv[5000000]=qpow(jc[5000000],mod-2);
    for(int i=5000000;i>=1;i--){
        inv[i-1]=inv[i]*i%mod;
    }
    inv[0]=1;
//  cout<<inv[2]<<' '<<inv[3]<<endl;
}
int C(int x,int y){
    if(y<0) return 0;
    if(y>x) return 0;
    return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
int n,m;
int include13,include13_fAKe;   //include13 代表第一次计算的答案 include13_fAKe 代表后面应当减去的答案  
#undef int
int main(){
    #define int long long
    init(); 
//  cout<<C(5,3)<<endl; 
    n=read(),m=read();
    //长度确定 和确定 最大值容斥 奇数个数较小 
    //和 为 3m 最大值 <=2m 奇数 <=m
    for(int i=0;i<=min(n,m);i++){
        if((3*m-i)%2!=0)    continue;
        //钦定数量的位置为奇数 然后是插板法 
        include13+=C(n,i)*C((3*m-i)/2+n-1,n-1)%mod;
        include13%=mod;
//      cout<<(3*m-i)/2+n<<' '<<n<<endl;
//      cout<<'&'<<include13<<endl;
    } 
    //第二部分 直接钦定一个位置为 2m+1 也就锁定了奇数最多 m 个 
    include13_fAKe=n*C(m+n-2,n-1)%mod;
    write2((include13-include13_fAKe+mod)%mod);
    return 0; 
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！