20231023 比赛总结

比赛链接

反思

A

花了很长时间，幸亏没怎么调就对了，以后还是应该先看其他题的
括号匹配题的套路感觉没有掌握透，感觉无非就是单调栈，哈希，折线图

B

感觉比 $T1$ 简单

C

正解还是很妙的，但 $68pts$ 的线段树优化建图很好拿（但不太好写）

D

感觉并不是那么难，用 $dp$ 化简多项式还是第一次见到

题解

A

考虑每个右括号只会匹配一个左括号，于是我们可以进行类似 $dp$ 的操作，我们记录每段区间的 $dp$ 值，可以发现每段区间只会有一个位置的 $dp$ 值 $>1$，其他都 $=1$，所以直接用单调栈维护即可
有些细节需要仔细想一下，也说不清
时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=10000100;
int n,x,y,z,m[2];
int c[N],lenth[N],f[N],top;
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;
}
int main(){freopen("brackets.in","r",stdin);freopen("brackets.out","w",stdout);n=read(),x=read(),y=read(),z=read(),m[0]=read(),m[1]=read(),c[0]=read(),c[1]=read();for(int i=2;i<n;i++) c[i]=(1ll*c[i-1]*x+1ll*c[i-2]*y+z)%m[i&1]+1;ull ans=0,tmp=0;for(int i=0;i<n;i++){if(~i&1) top++,lenth[top]=c[i],f[top]=tmp;else{tmp=0;while(top&&lenth[top]<=c[i]){c[i]-=lenth[top];ans+=lenth[top]+f[top];if(!c[i]) tmp=f[top]+1;top--;}if(top&&c[i]) lenth[top]-=c[i],ans+=c[i],tmp=1;}}printf("%llu\n",ans);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

B

用好 $a_i$ 互不相同的性质，发现只需要记录 $f_{i,S}$ 表示到 $i$，前一个与 $a_i$ 的异或值为 $S$ 的方案数
然后转移用前缀和优化可以到 $O(n{2}^m)$
但这样会考虑不到 $i$ 前一个不合法的情况，因为集合不相交，所以直接减掉即可
时间复杂度 $O(n{2}^m)$

#include <bits/stdc++.h>
using namespace std;
const int N=4100,MAXS=4100;
const int P=998244353;
int n,m,s,a[N],rev[MAXS],f[N][MAXS],g[N],tot[N],sum[N][MAXS];
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;
}
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){freopen("school.in","r",stdin);freopen("school.out","w",stdout);n=read(),m=read(),s=read();for(int i=1;i<=n;i++) a[i]=read(),rev[a[i]]=i;for(int i=1;i<=n;i++){tot[i]=tot[i-1];for(int S=0;S<1<<m;S++) sum[i][S]=sum[i-1][S];for(int S=0;S<1<<m;S++){int j=rev[S^a[i]];if(!j||j>=i) continue;f[i][S]=((1ll*tot[j-1]-sum[j-1][s^S]-g[j])%P+P)%P;inc(g[i],sum[j-1][s^S]);inc(tot[i],f[i][S]+j),inc(sum[i][S],f[i][S]+j);}}int ans=(n+n*(n-1)/2+1ll*n*(n-1)*(n-2)/6%P)%P;for(int i=1;i<=n;i++) for(int S=0;S<1<<m;S++) inc(ans,f[i][S]);printf("%d\n",ans);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

C

线段树优化建图的做法是显然的
考虑正解
我们假设我们有一张图，每个点都是指向 $1$ 个区间（多个也没事），且边权为 $1$，我们是否可以不建出图，$O(n)$ 求最短路
是可以的。我们只要用并查集维护这个点后面第一个未被访问到的点即可，然后在 $bfs$ 的过程中便可以合并并查集，然后做到 $O(n)$ 的复杂度（并查集不算）

但我们如何建出一个点指向区间的图呢
考虑做一个映射，我们令 $j$ 为 $id\%n$，把每个点归到类中去，那么类 $j$ 可以到 $[j-R,j-L]$ 的每一个类，这样就可以用上述方法 $O(n)$ 计算了
感觉还是很妙的

#include <bits/stdc++.h>
using namespace std;
const int N=1000100,inf=1e9;
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;
}
int dis[N<<1],ans[N];
int que[N],hh,tt;
int stk[N],hd,tl;
int fa[N];
int ne[N],h[N];
int get_father(int x){ return x==fa[x]?x:fa[x]=get_father(fa[x]);}
void insert(int l,int r,int Dist){for(int i=get_father(l);i<=r;i=get_father(i)){for(int u=h[i];~u;u=ne[u]) if(dis[u]==inf) dis[u]=Dist,que[++tt]=u;fa[i]=get_father(i+1);}
}
void work(){int n=read(),d=read(),L=read(),R=read(),q=read();for(int i=0;i<n;i++) h[i]=-1;for(int i=0;i<n;i++){int pos=1ll*i*d%n;ne[i]=h[pos],h[pos]=i;}for(int i=0;i<=n;i++) fa[i]=i;int D=R-L;for(int i=0;i<n;i++) dis[i]=inf;hh=0,tt=-1;dis[0]=0,que[++tt]=0;while(hh<=tt){int u=que[hh++];int t=(u-R+n)%n;if(t+D<n) insert(t,t+D,dis[u]+1);else insert(t,n-1,dis[u]+1),insert(0,D-(n-t),dis[u]+1);}for(int i=0;i<n;i++) dis[i+n]=dis[i];for(int i=0;i<n;i++) ans[i]=inf;hd=0,tl=-1;for(int i=2*n-1;i>=0;i--){if(i+L<2*n){while(hd<=tl&&dis[i+L]<=dis[stk[tl]]) tl--;stk[++tl]=i+L;}while(hd<=tl&&stk[hd]>i+R) hd++;if(hd<=tl&&i<n) ans[i]=dis[stk[hd]];}while(q--){int x=read();if(ans[x]>n+5) puts("-1");else printf("%d\n",ans[x]);}
}
int main(){freopen("calculator.in","r",stdin);freopen("calculator.out","w",stdout);int T=read();while(T--) work();    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

D

考虑到约数和函数具有积性，因为 $\prod a_i=m$，所以 $\prod \sigma (a_i)=\sigma (m)$
所以我们可以快速算出部分 $1$
对于部分 $2$，我们可以把它理解成多项式，然后把它拆开成若干个乘积
于是我们可以 $dp$ 求解
令 $f_{i,a,b,c}$ 表示到第 $i$ 个质数，前面选了 $a$ 个 $f0$，$b$ 个 $f1$，$c$ 个 $f2$ 的方案和
这个是好转移的，有以下三种情况

1. 不选这个质数
2. 新建一个 $f0$ 或 $f1$ 或 $f2$
3. 放在原先的 $f0$ 或 $f1$ 或 $f2$ 中

这都是可以快速转移的
最后求答案的时候只要把为 $1$ 的贡献计算进去即可
时间复杂度 $O(k^4)$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int K=110,P=998244353;
int p[K],f[2][K][K][K];
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;
}
inline void inc(int &x,int y){ x=(x+y)%P;}
int qmi(int a,int b){a%=P;int res=1;for(;b;b>>=1){if(b&1) res=res*a%P;a=a*a%P;}return res;
}
signed main(){freopen("product.in","r",stdin);freopen("product.out","w",stdout);int na=read(),nb=read(),f0=read(),f1=read(),f2=read();int k=read();for(int i=1;i<=k;i++) p[i]=read();f[0][0][0][0]=1;for(int i=0;i<k;i++){memset(f[~i&1],0,sizeof(f[~i&1]));int t=min(nb,i);for(int a=0;a<=t;a++) for(int b=0;b<=t-a;b++) for(int c=0;c<=t-a-b;c++){int coef=na%P*(p[i+1]+1)%P,rs=(nb-a-b-c)%P*f[i&1][a][b][c]%P*coef%P;inc(f[~i&1][a][b][c],f[i&1][a][b][c]);//不放入任何的集合inc(f[~i&1][a+1][b][c],rs*f0);//放入ainc(f[~i&1][a][b+1][c],rs*f1%P*p[i+1]);//放入binc(f[~i&1][a][b][c+1],rs*f2%P*p[i+1]%P*p[i+1]);//放入cinc(f[~i&1][a][b][c],(a+1ll*b*p[i+1]+1ll*c*p[i+1]%P*p[i+1])%P*coef%P*f[i&1][a][b][c]);//放入之前的集合} }int t=min(nb,k);int ans=0;for(int a=0;a<=t;a++) for(int b=0;b<=t-a;b++) for(int c=0;c<=t-a-b;c++)inc(ans,f[k&1][a][b][c]*qmi(f0+f1+f2,(nb-a-b-c)%(P-1))); printf("%d\n",ans);fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
/*
f[i][a][b][c]:在前i个质数中，有a个选了f0，b个选了f1，c个选了f2的权值和
*/