前言
T1 签了。
T2 一眼后缀数组板子，但是复杂度是 \(O(nq\log(n))\) 的，极限数据本地 \(4\) 秒，但如果您会 \(O(n)\) 求后缀数组的话就直接过掉了，但赛时数据貌似纯随机，遂可以直接过掉，可以优化成 \(O(n^2\log(n)+nq)\) 或 \(O(n^2\log(n)+q)\) 的，赛时想打这个但是怕常熟大和上面区别不大，遂没打，实际上第二种快得多，极限数据本地 \(500ms\)，正常评测姬都能过。
T3 想到建两棵 trie 树但是细节没想出来。
T4 想到对模数讨论，但不会 crt 遂根本没往那边想。
T1 02表示法
高精度加二进制分解板子，递归即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=610;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
string s; int tot,a[N],cnt[N],b[N][20];
bool big_than_0(string &s) {return s.size()>1||(s.size()==1&&s.back()!='0');}
void chu_2(string &s)
{
reverse(s.begin(),s.end());
for(int i=s.size()-1,now=0;i>=0;i--)
{
int x=s[i]-'0'+now*10,tmp=x>>1;
now=x-(tmp<<1),s[i]=tmp+'0';
}
while(s.size()>1&&s.back()-'0'==0) s.pop_back();
reverse(s.begin(),s.end());
}
void output(int x)
{
putchar_unlocked('2');
if(x==1) return ; putchar_unlocked('(');
if(x==0) return putchar_unlocked('0'),putchar_unlocked(')'),void();
memset(b[x],0,sizeof(b[x])),cnt[x]=0;
for(int i=0,y=x;y;i++,y>>=1) if(y&1) b[x][++cnt[x]]=i;
reverse(b[x]+1,b[x]+1+cnt[x]);
for(int i=1;i<=cnt[x];i++)
{
output(b[x][i]);
if(i!=cnt[x]) putchar_unlocked('+');
}
putchar_unlocked(')');
}
signed main()
{
freopen("pow.in","r",stdin),freopen("pow.out","w",stdout);
cin>>s;
for(int i=0;big_than_0(s);i++,chu_2(s))
if((s.back()-'0')&1) a[++tot]=i;
reverse(a+1,a+1+tot);
for(int i=1;i<=tot;i++)
{
output(a[i]);
if(i!=tot) putchar_unlocked('+');
}
}
T2 子串的子串
-
部分分 \(100pts\)：每次查询都重构一遍后缀数组，最后答案为 \(\dfrac{len\times (len+1)}{2}-\sum\limits_{i=l}^r{height_i}\)，\(O(nq\log(n))\)。
-
正解一：
考虑 \(q\) 很大 \(n\) 很小，所以会存在大量右端点重复的，所以总共只需要跑 \(n\) 遍后缀数组，对于右端点相同根据 \(lcp(sa_l,sa_r)=\min\limits_{i=l+1}^r{height_i}\)，套个 ST 表即可。
可以将左端点排序套链表做，也可以每个询问都 \(O(n)\) 跑一遍，前者复杂度为 \(O(n^2\log(n)+q)\)，后者为 \(O(n^2\log(n)+nq)\)，排序可以用桶排，后者就能过。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort #define pb push_back using namespace std; const int N=3010,M=2e4+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,m,mx[N],sa[N],rk[N],id[N],pos[N],cnt[N],key[N],ans[M],oldrk[N],height[N],mi[15][N]; char s[N],t[N]; struct aa {int l,id;}; vector<aa>e[N]; void count_sort(int len,int m) { memset(cnt,0,4*(m+1)); for(int i=1;i<=len;i++) cnt[key[i]]++; for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1]; for(int i=len;i>=1;i--) sa[cnt[key[i]]]=id[i],cnt[key[i]]--; } void init(char s[],int len) { int m=127,tot=0,num=0; for(int i=1;i<=len;i++) key[i]=rk[id[i]=i]=(int)s[i]; count_sort(len,m); for(int w=1;w<len&&tot!=len;w<<=1,m=tot) { num=0; for(int i=len;i>=len-w+1;i--) id[++num]=i; for(int i=1;i<=len;i++) if(sa[i]>w) id[++num]=sa[i]-w; for(int i=1;i<=len;i++) key[i]=rk[id[i]]; count_sort(len,m); for(int i=1;i<=len;i++) oldrk[i]=rk[i]; tot=0; for(int i=1;i<=len;i++) { tot+=(oldrk[sa[i]]!=oldrk[sa[i-1]]||oldrk[sa[i]+w]!=oldrk[sa[i-1]+w]); rk[sa[i]]=tot; } } for(int i=1,k=0;i<=len;i++) if(rk[i]) { for(k-=(!!k);s[i+k]==s[sa[rk[i]-1]+k];k++); height[rk[i]]=k; } memset(mi,0x3f,sizeof(mi)),memset(cnt,0,sizeof(cnt)); for(int i=1;i<=len;i++) mi[0][i]=height[i]; for(int i=1;i<=__lg(len);i++) for(int j=1;j<=len;j++) mi[i][j]=min(mi[i-1][j],mi[i-1][j+(1<<(i-1))]); } int lcp(int l,int r) {l++; int t=__lg(r-l+1); return min(mi[t][l],mi[t][r-(1<<t)+1]);} signed main() { freopen("substring.in","r",stdin),freopen("substring.out","w",stdout); read(n,m),scanf("%s",s+1); for(int i=1;i<=n;i++) mx[i]=i+1; for(int i=1,l,r;i<=m;i++) read(l,r),e[r].pb((aa){l,i}),mx[r]=min(mx[r],l); for(int r=1;r<=n;r++) { memset(t,0,sizeof(t)); for(int i=mx[r];i<=r;i++) t[i-mx[r]+1]=s[i]; init(t,r-mx[r]+1); for(auto x:e[r]) { int l=x.l,id=x.id,tot=0; ans[id]=(r-l+1)*(r-l+2)>>1; for(int i=l-mx[r]+1;i<=r-mx[r]+1;i++) pos[++tot]=rk[i]; for(int i=1;i<=tot;i++) cnt[pos[i]]++; tot=0; for(int i=1;i<=r-mx[r]+1;i++) for(;cnt[i];cnt[pos[++tot]=i]--); for(int i=2;i<=tot;i++) ans[id]-=lcp(pos[i-1],pos[i]); } } for(int i=1;i<=m;i++) write(ans[i]),puts(""); } -
正解二（官方正解）：
统计每个 \([l,r]\) 对答案的贡献，\(O(n^2)\) 预处理，\(O(1)\) 查询。
对于每个 \([l,r]\)，计算其哈希值，会有重复的，所以 \(ans_{l,r}+1,ans_{last_{hash(l,r)},r}-1\)，最后二维前缀和一下即可。
复杂度 \(O(n^2+q)\) 甚至没有后缀数组跑得快。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define endl '\n' #define sort stable_sort using namespace std; const int N=3010,B=29; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,m,ans[N][N]; char s[N]; unordered_map<ull,int>last; ull tmp,b[N],h[N]; void get_hash(char s[]) { b[0]=1; for(int i=1;i<=n;i++) b[i]=b[i-1]*B; for(int i=1;i<=n;i++) h[i]=h[i-1]*B+(s[i]-'a'); } ull ask(int l,int r) {return h[r]-h[l-1]*b[r-l+1];} signed main() { freopen("substring.in","r",stdin),freopen("substring.out","w",stdout); read(n,m),scanf("%s",s+1),get_hash(s); for(int i=1,vr=n;i<=n;i++,vr--,last.clear()) for(int l=1,r=i;r<=n;l++,r++) ans[last[tmp=ask(l,r)]][r]--,ans[l][r]++,last[tmp]=l; for(int l=n;l>=1;l--) for(int r=l;r<=n;r++) ans[l][r]+=ans[l+1][r]+ans[l][r-1]-ans[l+1][r-1]; for(int i=1,l,r;i<=m;i++) read(l,r),write(ans[l][r]),puts(""); }
T3 魔法咒语
建两棵trie 树，原串建一棵，反串建一棵。
那么在原树上遍历到节点 \(p\) 时，若他没有 \(c\) 儿子，就将反树中 \(c\) 的贡献加上。
这样会有两种情况考虑不到，一是原串可以被其自身前 \(len-1\) 个字符和最后一个字符拼出来，一是只有一个字符的串不可能被拼出来，特殊处理一下即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e4+10,M=4e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n; ll ans; bool vis[26],yet[26];
struct trie
{
int tot,son[M][26],cnt[26];
void insert(char s[],int len,bool d)
{
if(d) reverse(s,s+len);
for(int i=0,p=0,c;i<len;i++)
{
if(!son[p][c=s[i]-'a']) son[p][c]=++tot,cnt[c]++;
p=son[p][c];
}
}
}pre,suf;
signed main()
{
freopen("magic.in","r",stdin),freopen("magic.out","w",stdout);
read(n); char s[45];
for(int i=1,len;i<=n;i++)
{
scanf("%s",s),len=strlen(s),vis[s[len-1]-'a']=1;
pre.insert(s,len,0),suf.insert(s,len,1);
if(len==1&&!yet[s[0]-'a']) ans+=(yet[s[0]-'a']=1);
}
for(int p=1;p<=pre.tot;p++) for(int c=0;c<26;c++)
(!pre.son[p][c])?ans+=suf.cnt[c]:ans+=vis[c];
write(ans);
}
T4 表达式
对于模数很小的情况，我们可以建一棵线段树，\(val_{p,x}\) 表示在线段树节点 \(p\) 管辖区间内，输入的树是 \(x\) 的结果，显然有 pushup 为 \(val_{p,x}=val_{re,val_{ls,x}}\)，即先放到左边跑，再放到右边跑，叶子结点特殊处理。
那么对于模数很大的，发现数据中模数都是合数或很小的质数（前三个点暴力除外），考虑将其分解成几个较小的数的乘积，对于每个分解出的数跑线段树，最后用 crt 合并答案即可。
实现细节上，需要扩展欧拉定理，不然快速幂指数太大复杂度爆炸，所以要求出每个分解出的数的欧拉函数，由此求逆元又可以用快速幂了，不需要 exgcd，这样快速幂的 \(\log\) 直接变成常数级别，跑得飞快。
甚至为了做这题专门学了 crt 和扩欧。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int _,n,m,P,a[N],mod[5],phi[5],inv[5],val[N<<2][5][30]; char s[N];
ll qpow(ll a,int b)
{ll res=1; for(;b;(a*=a)%=P,b>>=1) if(b&1) (res*=a)%=P; return res;}
int qpow(int a,int b,int p)
{int res=1; for(;b;(a*=a)%=p,b>>=1) if(b&1) (res*=a)%=p; return res;}
void pushup(int p)
{
for(int i=1;i<=mod[0];i++) for(int j=0;j<mod[i];j++)
val[p][i][j]=val[rs][i][val[ls][i][j]];
}
void calc(int p,int x)
{
if(s[x]=='+') for(int i=1,tmp;i<=mod[0];i++)
{
tmp=a[x]%mod[i];
for(int j=0;j<mod[i];j++) val[p][i][j]=(j+tmp)%mod[i];
}
else if(s[x]=='*') for(int i=1,tmp;i<=mod[0];i++)
{
tmp=a[x]%mod[i];
for(int j=0;j<mod[i];j++) val[p][i][j]=j*tmp%mod[i];
}
else for(int i=1,tmp;i<=mod[0];i++)
{
tmp=a[x]?a[x]%phi[i]+phi[i]:0;
for(int j=0;j<mod[i];j++) val[p][i][j]=qpow(j,tmp,mod[i]);
}
}
void build(int p,int l,int r)
{
if(l==r) return calc(p,l),void();
build(ls,l,mid),build(rs,mid+1,r),pushup(p);
}
void change(int p,int l,int r,int x)
{
if(l==r) return calc(p,l),void();
x<=mid?change(ls,l,mid,x):change(rs,mid+1,r,x),pushup(p);
}
signed main()
{
freopen("expr.in","r",stdin),freopen("expr.out","w",stdout);
read(_,n,m,P); for(int i=1;i<=n;i++)
{
while(s[i]!='+'&&s[i]!='*'&&s[i]!='^') s[i]=getchar_unlocked();
read(a[i]);
}
if(_<=3)
{
ll x; for(int i=1,op;i<=m;i++)
{
read(op,x);
if(op&1)
{
for(int j=1;j<=n;j++)
s[j]=='+'?(x+=a[j])%=P:(s[j]=='*'?(x*=a[j])%=P:x=qpow(x,a[j]));
write(x),puts("");
}
else
{
for(s[x]=0;s[x]!='+'&&s[x]!='*'&&s[x]!='^';)
s[x]=getchar_unlocked();
read(a[x]);
}
}
return 0;
}
int x=P; for(int i=2,tmp=sqrt(P),sum;i<=tmp;i++) if(!(x%i))
{
for(sum=1;!(x%i);x/=i) sum*=i;
mod[++mod[0]]=sum,phi[mod[0]]=sum/i*(i-1);
}
if(x>1) mod[++mod[0]]=x,phi[mod[0]]=x-1;
for(int i=1;i<=mod[0];i++) inv[i]=qpow(P/mod[i],phi[i]-1,mod[i]);
build(1,1,n); for(int i=1,op,x;i<=m;i++)
{
read(op,x);
if(op&1)
{
int res=0; for(int j=1;j<=mod[0];j++)
(res+=P/mod[j]*inv[j]%P*val[1][j][x%mod[j]]%P)%=P;
write(res),puts("");
}
else
{
for(s[x]=0;s[x]!='+'&&s[x]!='*'&&s[x]!='^';)
s[x]=getchar_unlocked();
read(a[x]),change(1,1,n,x);
}
}
}