Submission #67004314

---

Source Code Expand

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define bi __int128_t
#define lb(x) ((x)&(-(x)))
#define gp(i,j) (((i)>>(j-1))&1)
#define ppc __builtin_popcount
#define ctz __builtin_ctz
#define db long double
using namespace std;
const int N=5e5+10,mod=998244353,inf=1e9+10;
const db eps=1e-8;
bool Mbg;
void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;}
void Sub(int &a,int b){a-=b;if(a<0) a+=mod;}
void Mul(int &a,int b){a=1ll*a*b%mod;}
int qp(int a,int b){
    int x=1;
    while(b){
        if(b&1) Mul(x,a);
        Mul(a,a);b>>=1;
    }return x;
}
int p2[N];
struct Trie{
    int T[N][2];int tot=1;
    int f[N],g[N],c[N];
    void init(){g[0]=1;}
    void upd(string s){
        vector<int> pos;
        int now=1;pos.push_back(now);
        for(auto ch:s){
            int o=ch-'A';
            if(!T[now][o]) T[now][o]=++tot;
            now=T[now][o];
            pos.push_back(now);
        }reverse(pos.begin(),pos.end());
        c[now]++;
        for(auto ed:pos){
            f[ed]=1ll*f[T[ed][0]]*f[T[ed][1]]%mod;
            g[ed]=1ll*g[T[ed][0]]*g[T[ed][1]]%mod;
            //cout<<ed<<' '<<T[ed][0]<<' '<<f[ed]<<' '<<g[ed]<<endl;
            int w=(g[ed]+mod-f[ed])%mod;
            Mul(g[ed],p2[c[ed]]);
            f[ed]=(g[ed]+mod-w)%mod;
        }
    }
}T;
int n;
string st[N];
void slv(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>st[i];
    p2[0]=1;
    for(int i=1;i<=n;i++) p2[i]=2ll*p2[i-1]%mod;
    T.init();
    for(int i=1;i<=n;i++){
        T.upd(st[i]);
        cout<<T.f[1]<<endl;
    }
}
bool Med;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;//cin>>t;
    while(t--) slv();
    cout.flush();
    cerr<<clock()*1.0/CLOCKS_PER_SEC<<' '<<(&Mbg-&Med)/1024.0/1024.0<<endl;
    return 0;
}

Submission Info

Judge Result