2024ICPC网络赛2记录：CK

这一次网络赛我们过8题，排名71，算是发挥的非常好的了。这一把我们三个人手感都很好，前六题都是一遍过，然后我又切掉了非签到的E和C，最后时间不是很多，K只想到大概字典树的思路，细节不是很懂就直接开冲，当然是没有冲出来。

C：
感觉思路挺容易的，但是我想了很久，如果我能秒掉这种题（当然我觉得实力不够秒掉这种题）有可能可以再把K开出来。

首先，我们肯定是要维护当前有哪些后缀能和前缀匹配的。
我们想了很多错误的思路以后才开始思考kmp，然后就想到了可以一直跳kmp，只需要把相同的合并起来，如果能匹配的就全部一起跳过，不匹配的就直接删掉，时间复杂度O(n)。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
#define ull unsigned long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=3e5+10;
int n;ll ans,a[N],b[N],c[N];
int f[N],g[N];
void solve(){qr(n);  ll tot=0;rep(i,1,n){qr(c[i]),qr(a[i]),qr(b[i]);c[i]=(c[i]+ans)%n;if(i==1)tot+=b[i];else{if(c[1]==c[i])tot+=b[i];int j=f[i-1];if(c[i]==c[j+1])g[i-1]=g[j];else g[i-1]=f[i-1];while(j){if(c[j+1]!=c[i]){tot-=b[i-j];j=f[j];}else break;}if(c[j+1]==c[i])f[i]=j+1;else f[i]=j;while(j){if(c[j+1]==c[i])j=g[j];else{tot-=b[i-j];j=f[j];}}}ans+=tot*a[i];qw(ans);puts("");}
}
int main(){int tt;tt=1;while(tt--)solve();return 0;
}

K
看上去要求某种匹配数的个数，有点吓人。
不过看到异或就知道这个异或肯定不是白给你的，大概就是用字典树，一开始我以为是把两个数组分开建字典树，后面发现要一起建，然后就想到用dp来维护。不过我的dp始终是4维的，优化不到三维，后面上网看了一下，发现全部都是四维，那我就直接交了。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
#define ull unsigned long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=210;
const int mod=998244353;
struct node{int f[N];node(){memset(f,0,sizeof(f));}void print(){rep(i,0,10)cout<<f[i]<<" ";cout<<endl;}
};
int n;ll k;
ll a[N],b[N],c[N];
int fc[N],ifc[N];
int power(int a,int b){int ret=1;while(b){if(b&1)ret=1ll*ret*a%mod;a=1ll*a*a%mod;b>>=1;}return ret;
}
int C(int x,int y){if(x<0||y<0||x<y)return 0;return 1ll*fc[x]*ifc[y]%mod*ifc[x-y]%mod;
}
int A(int x,int y){if(x<0||y<0||x<y)return 0;return 1ll*fc[x]*ifc[x-y]%mod;
}
node solve(int ki,int l,int r,int x,int y){if(l>r||x>y){node now;now.f[0]=1;return now;}if(ki==-1){node now;int t=min(r+1-l,y+1-x);rep(i,0,t)now.f[i]=1ll*C(r-l+1,i)*A(y-x+1,i)%mod;return now;}//sortint mid1=l-1,mid2=x-1;rep(i,l,r){if(a[i]>>ki&1)break;mid1=i;}rep(i,x,y){if(b[i]>>ki&1)break;mid2=i;}if(k>>ki&1){node ans1=solve(ki-1,l,mid1,mid2+1,y);node ans2=solve(ki-1,mid1+1,r,x,mid2);node ans;int siz1=min(mid1+1-l,y-mid2);int siz2=min(r-mid1,mid2+1-x);rep(i,0,siz1)rep(j,0,siz2)(ans.f[i+j]+=1ll*ans1.f[i]*ans2.f[j]%mod)%=mod;return ans;}else{node ans1=solve(ki-1,l,mid1,x,mid2);node ans2=solve(ki-1,mid1+1,r,mid2+1,y);node ans;int siz1=min(mid1+1-l,mid2+1-x);int siz2=min(r-mid1,y-mid2);rep(i,0,siz1){int x1=mid1+1-l-i,y1=mid2+1-x-i;rep(j,0,siz2){int x2=r-mid1-j,y2=y-mid2-j;int t1=min(x1,y2);int t2=min(x2,y1);rep(p1,0,t1){rep(p2,0,t2){(ans.f[i+j+p1+p2]+=1ll*ans1.f[i]*ans2.f[j]%mod*C(x1,p1)%mod*A(y2,p1)%mod*C(x2,p2)%mod*A(y1,p2)%mod)%=mod;}}}}return ans;}
}
void solve(){qr(n),qr(k);rep(i,1,n)qr(a[i]);rep(i,1,n)qr(b[i]);sort(a+1,a+n+1);sort(b+1,b+n+1);node ans=solve(61,1,n,1,n);rep(i,1,n)qw(ans.f[i]),puts("");
}
int main(){fc[0]=1;rep(i,1,200)fc[i]=1ll*fc[i-1]*i%mod;ifc[200]=power(fc[200],mod-2);dwn(i,199,0)ifc[i]=1ll*ifc[i+1]*(i+1)%mod;int tt;tt=1;while(tt--)solve();return 0;
}