8.16 提高组模拟赛

T1

跳过，普通 BFS，大概黄到绿。

T2

数论题，要求输出每一次操作，结合数据范围，显然不是通过神秘推导跳过中间步骤的，可能是递推。

对于 n+1，可以通过帕斯卡恒等式得到：

对于 m+1，可以直接拆开再合并，得到：

可以发现，我们想要递推，需要知道三个量：

• \sum_{i=0}^m C_n^i（后记为 A）
• \sum_{i=0}^{m-1}+ C_n^i（后记为 B）
• 组合数

为了复杂度正确，需要做到 O(1) 求组合数，在这里，我们可以使用阶乘逆元预处理好。

通过一点点卡常，就可以做到 610 毫秒秒杀本题。

未卡常代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MN=2e6+10;
const int MOD=998244353;
int T,n,m,op[MN],fact[MN],ifact[MN],pw[MN],A,B;

int fastpow(int a,int b,int mod){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int C(int n,int k){
    if(k<0||k>n) return 0;//特判
    return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
}

signed main(){
    freopen("t2.in","r",stdin);
    freopen("t2.out","w",stdout);

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>T>>n>>m;

    for(int i=1;i<=T;i++) cin>>op[i];

    fact[0] = 1;
    for(int i = 1; i < MN; i++) fact[i] = fact[i-1] * i % MOD;

    ifact[MN-1]=fastpow(fact[MN-1],MOD-2,MOD);
    for(int i=MN-1;i>=1;i--) ifact[i-1]=ifact[i]*i%MOD;

    pw[0]=1;
    for(int i=1;i<MN;i++) pw[i]=pw[i-1]*2%MOD;

    //处理A
    if(m>=n) A=pw[n];
    else {
        for(int i=0;i<=m;i++){
            A+=C(n,i);
            if(A>MOD) A-=MOD;
        }
    }

    //处理B
    if(m<=n){
        B=(A-C(n,m))%MOD;
        if(B<0) B+=MOD;
    }else B=pw[n];

    //处理询问
    for(int i=1;i<=T;i++){
        if(op[i]==1){
            n++;
            int A_new=A+B,B_new,tmp=C(n,m);
      
            if(A_new>=MOD) A_new-=MOD;

            B_new=A_new-tmp;
            if(B_new<0) B_new+=MOD;

            A = A_new;
            B = B_new;
        }else{
            m++;
            int tmp=C(n,m),A_new=A+tmp,B_new=A;

            if(A_new>=MOD) A_new-=MOD;

            A=A_new;
            B=B_new;
        }
        cout<<A<<"\n";
    }
    return 0;
}