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;
}
//sort
int 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;
}