2023大联盟8 比赛总结

大联盟8 比赛总结"/>

2023大联盟8 比赛总结

比赛经历

有点忘了，稍微写一些
本来早上有 n f l s nfls nfls 的，但因为今天大联盟 T 1 T1 T1 是我们学校的题，于是写大联盟
第一题因为下午要我们讲，所以讨论了一下做法，个人感觉第一步把 a + b + a a+b+a a+b+a 拆成 a + b a+b a+b 和 a a a 两个不关联的部分很妙，其他随便贪或者我比较蠢，写了决策单调性优化 d p dp dp
大概过了 40 m i n 40min 40min
T 2 T2 T2 是串串题，看了一遍没什么思路，于是跳
接下来就是恶心的部分了
我 C C C 题一眼想到一个 n m 2 nm^2 nm2 的 d p dp dp，遂写，发现过了样例，考虑优化时一眼卷积，于是便直接开始打 n t t ntt ntt，打完之后发现坏了，模数是 1 e 9 + 7 1e9+7 1e9+7，改成 f f t fft fft 之后精度掉没了，这时大概 2 h 2h 2h
其他人 T 3 T3 T3 也没思路，分享了一下解法，我觉得还是我的 n 3 n^3 n3 比较简单，但始终优化不到 O ( n 2 ) O(n^2) O(n2)，没办法，拼了个 m = 1145141919 m=1145141919 m=1145141919 的部分分上去
其实一开始我就大概知道 T 4 T4 T4 题意了，因为有人开 T 4 T4 T4 把题意报出来了，我感觉很不可做，于是就没细想
预估分数： 100 + 0 + 40 + 0 = 140 100+0+40+0=140 100+0+40+0=140
实际分数： 100 + 0 + 25 + 0 = 125 100+0+25+0=125 100+0+25+0=125
T 3 T3 T3 特殊性质拼错了，还是要二项式反演

反思

今天题感觉做着很难绷，没有一道题我是有十足的把握能够在赛场上场切的，感觉遗憾就是 T 3 T3 T3 没看到模数 1 e 9 + 7 1e9+7 1e9+7 然后浪费了 $4 0 m i n 0min 0min

题解

T1

把 a , b , a a,b,a a,b,a 拆成 a + b a+b a+b 和 a a a，然后直接贪即可
我是写的决策单调性优化 d p dp dp，因为 a + b a+b a+b 选的个数一定不降
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100100,M=1000100;
int n,m,ans[M],a[N],b[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void solve(int l,int r,int ql,int qr){if(l>r) return;int mid=(l+r)>>1;int pos=ql;for(int i=ql;i<=qr;i++){if(mid-2*i<0) break;int val=b[i]+a[mid-2*i];if(val>b[pos]+a[mid-2*pos]) pos=i;}ans[mid]=b[pos]+a[mid-2*pos];solve(l,mid-1,ql,pos),solve(mid+1,r,pos,qr);
}
signed main(){freopen("coin.in","r",stdin);freopen("coin.out","w",stdout);n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) b[i]=read()+a[i];sort(a+1,a+n+1,greater<int>()),sort(b+1,b+n+1,greater<int>());for(int i=1;i<=n;i++) a[i]+=a[i-1],b[i]+=b[i-1];solve(1,min(m,3*n),0,n);int ANS=0;for(int i=1;i<=min(m,3*n);i++) ANS^=ans[i];for(int i=3*n+1;i<=m;i++) ANS^=ans[3*n];printf("%lld\n",ANS);return 0;
}

T2

感觉很有意思的一道题
首先一个结论是每个串的开头都是 T 0 T_0 T0​
考虑贡献只有可能是在两串交接处和末串与 D D D 的交接处和 D D D 内部
我们记 m x s u f i mxsuf_i mxsufi​ 表示 T i T_i Ti​ 末尾与 S S S 的开头最多匹配的长度，每次只要跳 b o r d e r border border 就可以找到所有合法串，因为 T 0 T_0 T0​ 是已知的一串开头，所以我们可以预处理出 t o t i tot_i toti​ 表示 m x s u f = i mxsuf=i mxsuf=i 的匹配的个数
然后我们只要用类似 k m p kmp kmp 的方式暴力一个一个跳 D D D 即可
至于预处理我用的是字符串哈希进行匹配
细节有些多，时间复杂度 O ( ∑ ∣ D ∣ ) O(\sum |D|) O(∑∣D∣)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2000100;
typedef unsigned long long ull;
ull v[2][2],base[2]={1331,131},hS[2][N],hT[2][N],bs[2][N];
int n,mxsuf[N],tot[N];
ull ans[N];
int neS[N],fail[N][2];
int lens,lent0;
char t0[N],s[N],D[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
ull gethash(int l,int r,int t,ull *h){ return h[r]-h[l-1]*bs[t][r-l+1];}
void init(){lens=strlen(s+1);for(int i=2,j=0;i<=lens;i++){while(j&&s[j+1]!=s[i]) j=neS[j];if(s[j+1]==s[i]) j++;neS[i]=j;}for(int i=1;i<=lens;i++){int c=s[neS[i]+1]-48;fail[i][c]=neS[i],fail[i][c^1]=fail[neS[i]][c^1];}v[0][0]=mrand(),v[0][1]=mrand(),v[1][0]=mrand(),v[1][1]=mrand();lent0=strlen(t0+1);for(int i=1;i<=lent0;i++) for(int t:{0,1}) hT[t][i]=hT[t][i-1]*base[t]+v[t][t0[i]-48];for(int i=1;i<=lens;i++) for(int t:{0,1}) hS[t][i]=hS[t][i-1]*base[t]+v[t][s[i]-48];bs[0][0]=bs[1][0]=1;for(int i=1;i<=lens;i++) for(int t:{0,1}) bs[t][i]=bs[t][i-1]*base[t];for(int i=1;i<=lens;i++){if(hT[0][lens-i]==gethash(i+1,lens,0,hS[0])&&hT[1][lens-i]==gethash(i+1,lens,1,hS[1])) tot[i]=1;tot[i]+=tot[neS[i]];}for(int i=lens-1;i;i--) if(hS[0][i]==gethash(lent0-i+1,lent0,0,hT[0])&&hS[1][i]==gethash(lent0-i+1,lent0,1,hT[1])){ mxsuf[0]=i;break;}for(int i=1;i<=lent0-lens+1;i++) if(gethash(i,i+lens-1,0,hT[0])==hS[0][lens]&&gethash(i,i+lens-1,1,hT[1])==hS[1][lens]) ans[0]++;
}
int main(){freopen("string.in","r",stdin);freopen("string.out","w",stdout);n=read();scanf("%s",s+1),scanf("%s",t0+1);init();for(int i=1;i<=n;i++){int k=read(),pre=-1;while(k--){int id=read();ans[i]+=ans[id];if(pre!=-1) ans[i]+=tot[mxsuf[pre]];pre=id;}scanf("%s",D+1);int lenD=strlen(D+1);mxsuf[i]=mxsuf[pre];for(int j=1;j<=lenD;j++){if(D[j]==s[mxsuf[i]+1]) mxsuf[i]++;else{mxsuf[i]=fail[mxsuf[i]][D[j]-48];if(D[j]==s[mxsuf[i]+1]) mxsuf[i]++;}if(mxsuf[i]==lens) ans[i]++,mxsuf[i]=neS[mxsuf[i]];}}for(int i=1;i<=n;i++) printf("%llu\n",ans[i]);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

C

w x q n b ! ! ! wxq\;nb!!! wxqnb!!!
我也不知道 w x q wxq wxq 怎么想到的）用 E G F EGF EGF 求解
我忘了式子怎么推的了（。。。）
反正最后的式子是 ∑ S = 0 2 n − 1 ( − 1 ) p o p c n t ( S ) S . . . \sum\limits_{S=0}^{2^n-1}(-1)^{popcnt(S)}S... S=0∑2n−1​(−1)popcnt(S)S...
然后好像是二项式定理展开，再分治 d p dp dp 解决
我不记得了，改天再问一下他怎么做
时间复杂度 O ( n 2 l o g n ) O(n^2logn) O(n2logn)

#include <bits/stdc++.h>
using namespace std;
const int N=2100,P=1e9+7;
int n,m,f[N][N],g[N],h[(1<<20)+5];
int pw2[N*N],C[N][N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void solve(int n){if(!n||n==1) return;solve(n/2);for(int i=0;i<=m;i++)for(int j=0;j<=i;j++) f[n][i]=(f[n][i]+1ll*f[n/2][j]*f[n/2][i-j]%P*C[i][j]%P*pw2[j*(n/2)])%P;if(n&1){for(int i=0;i<=m;i++){g[i]=0;for(int j=0;j<=i;j++) g[i]=(g[i]+1ll*f[n][j]*f[1][i-j]%P*C[i][j]%P*pw2[j])%P;}for(int i=0;i<=m;i++) f[n][i]=g[i];}
}
int qmi(int a,int b){int res=1;for(;b;b>>=1){if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}return res;
}
void fwt(){for(int mid=1;mid<1<<n;mid<<=1)for(int i=0;i<1<<n;i+=mid<<1) for(int j=0;j<mid;j++) h[i+j+mid]=(h[i+j+mid]+h[i+j])%P;
}
void work_sb(){pw2[0]=1;for(int i=1;i<=n;i++) pw2[i]=pw2[i-1]*2%P;for(int S=0;S<1<<n;S++){int res=0;for(int i=0;i<n;i++) if(S>>i&1) res+=pw2[i];h[S]=qmi(res,m);}for(int S=0;S<1<<n;S++) if(__builtin_popcount(S)&1) h[S]=(P-h[S])%P;fwt();if(n&1) printf("%d\n",(P-h[(1<<n)-1])%P);else printf("%d\n",h[(1<<n)-1]);
}
int main(){freopen("glass.in","r",stdin);freopen("glass.out","w",stdout);n=read(),m=read();if(m==1145141919){ work_sb();exit(0);}C[0][0]=1;for(int i=1;i<=m;i++) for(int j=0;j<=i;j++) C[i][j]=(!j||i==j)?1:(C[i-1][j-1]+C[i-1][j])%P;pw2[0]=1;for(int i=1;i<=m*n;i++) pw2[i]=pw2[i-1]*2%P;f[0][0]=1;for(int i=1;i<=m;i++) f[1][i]=P-1;solve(n);if(n&1) printf("%d\n",(P-f[n][m])%P);else printf("%d\n",f[n][m]);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

D

大分块题，狗都不补！！！