2021年CCPC网络预选赛重赛补题

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5+10;
    string xx=" nunhehheh";
    #define int long long
    const int mod=998244353;
    int T;
    int dp[N][10];
    int cnta[N];
    int pow2[N];
    signed main(){
    pow2[0]=1;
    for(int i=1;i<N;i++)pow2[i]=(pow2[i-1]*2 )%mod;
    cin>>T;
    while(T--){
        memset(cnta,0,sizeof cnta);
        string s;
        cin>>s;
        s=" "+s;
        int n=s.size()-1;
        
        for(int i=n;i>=2;i--)cnta[i-1]=cnta[i]+(s[i]=='a');
        // for(int i=1;i<=n;i++)cout<<cnta[i]<<" ";
        // cout<<endl;
        memset(dp,0,sizeof dp);
        int ans=0;
        //dp[0][0]=1;
        for(int i=0;i<=n;i++)dp[i][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=9;j++){
                dp[i][j]=dp[i-1][j];
                if(s[i]==xx[j]){
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
                    if(j==9)ans=(ans + dp[i-1][j-1]*(pow2[cnta[i]]-1))%mod;
                    //这个点的后面有多少个a
                }
            }
        }
        cout<<ans<<endl;
    }
    }