青蛙
又是青蛙跳石头的题，还是考虑贪心。。。
如果一只青蛙必须要花钱，可以考虑让它直接从1跳到n点
将石头与青蛙分别排序，二分最多能免费多少只青蛙，
发现这些青蛙一定能占满所有石头。剩下青蛙直接从1跳到n
特判一只都不能免费的情况，此时直接让花费最小的把石头跳完
一起自习的日子
考察伯努利数和调换枚举顺序的技巧。
其实就是拿伯努利数一直换来换去，最后打一个记搜
$\sum\limits_{i=0}^{n} \sum\limits_{j=1}^{a+id} \sum\limits_{l=1}^{j}l^{k}$
用自然数幂和公式化掉最后一个$\sum$
变为求
$\sum\limits_{i=0}^{n} \sum\limits_{j=1}^{a+i} j^k$
然后再用自然数幂和公式，化掉后一个$\sum$
变为求
$\sum\limits_{i=0}^{n} (a+id)^k$
发现没法直接用自然数幂和公式，那就先用二项式定理展开，再化
展开：
$\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{k}\binom{k}{j}a^{k-j}d^{j}i^{j}$
然后再对$i^j$用自然数幂和。
1 #include<bits/stdc++.h>
2
3 #define N 3050
4 #define LL long long
5
6 const int mod=1234567891;
7
8 using namespace std;
9
10 int k,a,n,d;
11 int inc[N],inv[N],iv[N],b[N];
12 int r[N],f[N],g[N],pa[N],pd[N],pn[N];
13
14 inline LL qpow(LL d,LL z){
15 LL ret=1;
16 for(;z;z>>=1,d=d*d%mod)
17 if(z&1)ret=ret*d%mod;
18 return ret;
19 }
20
21 inline void modd(LL &x){if(x>=mod)x-=mod;}
22
23 inline int C(int n,int m){
24 return 1ll*inc[n]*inv[m]%mod*inv[n-m]%mod;
25 }
26
27 inline int R(int j){
28 if(r[j])return r[j];
29 LL ans=0;
30 for(int l=0;l<=j;++l,modd(ans))
31 ans+=1ll*C(j+1,l)*b[l]%mod*pn[j+1-l]%mod;
32 r[j]=ans*iv[j+1]%mod;
33 if(!j)++r[j];
34 return r[j];
35 }
36
37 inline int F(int k){
38 if(f[k])return f[k];
39 LL ans=0;
40 for(int j=0;j<=k;++j,modd(ans))
41 ans+=1ll*C(k,j)*pa[k-j]%mod*pd[j]%mod*R(j)%mod;
42 return f[k]=ans;
43 }
44
45 inline int G(int k){
46 if(g[k])return g[k];
47 LL ans=0;
48 for(int l=k;~l;--l,modd(ans)){
49 ans+=1ll*C(k+1,l)*b[l]%mod*F(k+1-l)%mod;
50 }
51 g[k]=1ll*ans*iv[k+1]%mod;
52 return g[k];
53 }
54
55 inline void init(const int n){
56 inc[0]=inv[0]=iv[0]=iv[1]=1;
57 for(int i=1;i<=n;++i)inc[i]=1ll*inc[i-1]*i%mod;
58 inv[n]=qpow(inc[n],mod-2);
59 for(int i=n-1;i;--i)
60 inv[i]=1ll*inv[i+1]*(i+1)%mod,
61 iv[i+1]=1ll*inv[i+1]*inc[i]%mod;
62
63 b[0]=1;
64 for(int i=1;i<n;++i){
65 for(int j=0;j<i;++j)
66 b[i]=(1ll*C(i+1,j)*b[j]+b[i])%mod;
67 b[i]=-b[i];
68 b[i]=1ll*iv[i+1]*b[i]%mod+mod;
69 }
70 // cout<<b[3000]<<endl;
71 b[1]=iv[2];
72 }
73
74 inline void init2(const int m){
75 pa[0]=pd[0]=pn[0]=1;
76 for(int i=1;i<=m;++i){
77 pa[i]=1ll*pa[i-1]*a%mod;
78 pd[i]=1ll*pd[i-1]*d%mod;
79 pn[i]=1ll*pn[i-1]*n%mod;
80 }
81 memset(r,0,sizeof(int)*(m+1));
82 memset(f,0,sizeof(int)*(m+1));
83 memset(g,0,sizeof(int)*(m+1));
84 }
85
86 inline void work(){
87 scanf("%d%d%d%d",&k,&a,&n,&d);
88 init2(k+10);LL ans=0;
89 for(int l=k;~l;--l,modd(ans)){
90 ans+=1ll*C(k+1,l)*b[l]%mod*G(k+1-l)%mod;
91 }
92 ans=1ll*ans*iv[k+1]%mod;
93 printf("%lld\n",ans);
94 }
95
96 int main(){
97 init(3020);
98 int T;scanf("%d",&T);
99 while(T--)work();
100 return 0;
101 }
View Code
字符串
建立$S$的后缀自动机。对于$SAM$上的每个点$x$,维护它$right$集合中最后的位置,记为$last[x]$。
考虑插入一个字符会发生什么,设插入完$S$的长度为$len$。
有两种可能:
第一种:在fail树上加入一个叶子节点,设这个点是$np$。然后把这个点到根的路径上的所有点的$last$改为$len$。
第二种:把一个点$x$和$fail[x]$这条边上新加一个点$u$,使得$last[u]=last[x]$。
考虑len这个位置对答案的贡献,维护$ans[r][l]$表示$[l,r]$这个区间的答案。
一开始,先让$ans[len][l]=ans[len-1][l]$。显然第二种操作不会对$ans$有任何影响。
对于第一种操作,考虑$np$到根上的路径上的一个点$p$,$p$这个点当前的$last$为$last[p]$
(即被改成$len$之前),$p$这个点代表的字符串的最长长度为$len[p]$。考虑$ans[len]$会怎么改。
对于$l∈[1,last[p]-len[p]],ans[len][l]$和$len$取$max$,即对一个常数取$max$。
对于$l∈[last[p]-len[p]+1,last[p]]$,和$l-last[p]+1$取$max$,即对一段等差数列取$max$。
这样暴力做的复杂度是$O(n^3)$的。
第一种操作(就是把一个点到根的路径上的所有点搞成一个值),等价于把这个点$access$
第二种操作$lct$也可以轻松维护,不过要讨论$x$和$fail[x]$是否在同一条重链上
那么这样做的话,同一条重链上的点的$last$都是一样的。
所以对于重链对应的那棵$splay$的根,维护一下这条重链的所有点的$last$
那么对于$ans$的修改怎么搞?可以用可持久化线段树维护。
显然对于一条重链我们只需要关注它的$len$的最大值,并且只有在轻重儿子交换的时候再进行修改。
注：轻重儿子交换时应先让它处于无右儿子的状态，更新答案后再加新的右儿子，否则维护的信息就是错的
这样的话修改等价于一段区间对一个数取$max$,对一段等差数列取$max$。而这些都是很经典的操作
然后卡一下空间就可过了。具体实现见代码
还有一种二分的打法
在access修改一条重链的时候,直接在（这条重链的last位置）和
（这条重链上的所有点的len的最大值）取个max
即主席树单点修改，单点权值为这个点与后面的点的最长匹配长度
二分答案，check时区间查询最值是否大于二分的mid
1 #include<bits/stdc++.h>
2 #define N 200050
3 using namespace std;
4 char s[N];
5 int m,n,A;
6 struct node{
7 int len,fa,las;
8 int ch[26];
9 }tr[N];
10 int las=1,tot=1;
11 namespace seg{
12 int lc[N*100],rc[N*100],ma[N*100],rt[N],tot;
13 inline void upd(int g){ma[g]=max(ma[lc[g]],ma[rc[g]]);}
14 inline void add(int &g,int f,int l,int r,int pos,int tag,int lim){
15 if(f<=lim)g=++tot;
16 else g=f;
17 lc[g]=lc[f];rc[g]=rc[f];
18 ma[g]=ma[f];
19 if(l==r){ma[g]=max(ma[g],tag);return;}
20 const int m=l+r>>1;
21 if(pos<=m)add(lc[g],lc[f],l,m,pos,tag,lim);
22 else add(rc[g],rc[f],m+1,r,pos,tag,lim);
23 upd(g);
24 }
25 inline int ask(int g,int l,int r,int x,int y){
26 if(!g||l>y||r<x)return 0;
27 if(l>=x&&r<=y)return ma[g];
28 const int m=l+r>>1;
29 int r1=ask(lc[g],l,m,x,y),r2=ask(rc[g],m+1,r,x,y);
30 return max(r1,r2);
31 }
32 }
33 namespace lct{
34 int fa[N],ch[N][2],las[N],t1[N],len[N],ma[N];
35 inline bool Get(int x){return ch[fa[x]][1]==x;}
36 inline bool nroot(int x){
37 return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
38 }
39 inline void pr(int x){
40 printf("x:%d lc:%d rc:%d t1:%d las:%d len:%d ma:%d\n",x,ch[x][0],ch[x][1],t1[x],las[x],len[x],ma[x]);
41 }
42 inline void upd(int x){
43 ma[x]=len[x];
44 ma[x]=max(ma[x],ma[ch[x][0]]);
45 ma[x]=max(ma[x],ma[ch[x][1]]);
46 }
47 inline void push1(int x,int num){
48 if(!x)return;
49 t1[x]=las[x]=num;
50 }
51 inline void down(int x){
52 if(t1[x])push1(ch[x][0],t1[x]),push1(ch[x][1],t1[x]),t1[x]=0;
53 }
54 inline void rotate(int x){
55 int y=fa[x],z=fa[y],p=Get(x),w=ch[x][p^1];
56 if(w)fa[w]=y;ch[y][p]=w;
57 if(nroot(y))ch[z][Get(y)]=x;fa[x]=z;
58 fa[y]=x;ch[x][p^1]=y;
59 upd(y);upd(x);
60 }
61 void pushall(int x){
62 if(nroot(x))pushall(fa[x]);down(x);
63 }
64 inline void splay(int x){
65 pushall(x);
66 while(nroot(x)){
67 if(nroot(fa[x]))
68 rotate(Get(fa[x])==Get(x)?fa[x]:x);
69 rotate(x);
70 }
71 }
72 inline void access(int x,int n){
73 seg::rt[n]=seg::rt[n-1];
74 int lim=seg::tot;
75 for(int y=0,p;x;y=x,x=fa[x]){
76 splay(x);ch[x][1]=0;upd(x);
77 if(las[x]&&ma[x])
78 seg::add(seg::rt[n],seg::rt[n],1,A,las[x],ma[x],lim);
79 ch[x][1]=y;upd(x);
80 }
81 }
82 inline void link(int x,int y){fa[x]=y;}
83 inline void cut(int x,int p){fa[ch[x][p]]=0;ch[x][p]=0;upd(x);}
84 }
85
86 inline void add(int c,int n){
87 int p=las,np=++tot;
88 tr[np].len=tr[las].len+1;las=np;
89 lct::len[np]=tr[np].len;lct::upd(np);
90
91 for(;p&&!tr[p].ch[c];p=tr[p].fa)tr[p].ch[c]=np;
92 if(!p){
93 tr[np].fa=1;
94 lct::link(np,1);
95 lct::access(np,n);
96 lct::splay(np);
97 lct::push1(np,n);
98 return;
99 }
100 int q=tr[p].ch[c];
101 if(tr[q].len==tr[p].len+1){
102 tr[np].fa=q;
103 // cout<<"n::"<<n<<endl;
104 lct::link(np,q);
105 lct::access(np,n);lct::splay(np);lct::push1(np,n);
106
107 return;
108
109 }
110 int nq=++tot;
111 tr[nq]=tr[q];
112 tr[nq].len=tr[p].len+1;
113 tr[q].fa=tr[np].fa=nq;
114 for(;p&&tr[p].ch[c]==q;p=tr[p].fa)tr[p].ch[c]=nq;
115 lct::len[nq]=tr[nq].len;lct::upd(nq);
116
117 lct::splay(q);
118 if(lct::ch[q][0]){
119 lct::splay(tr[nq].fa);
120 lct::cut(tr[nq].fa,1);
121 }
122 lct::link(q,nq);lct::link(np,nq);
123 lct::link(nq,tr[nq].fa);
124 lct::las[nq]=lct::las[q];
125 lct::access(np,n);lct::splay(np);lct::push1(np,n);
126
127 }
128 int main(){
129 scanf("%s%d",s+1,&m);n=strlen(s+1);
130 A=n+m;
131 for(int i=1;i<=n;++i)add(s[i]-'a',i);
132 //,cout<<seg::ask(seg::rt[i],1,A,1)<<endl;
133 for(int i=1,op,x,y,ans=0;i<=m;++i){
134 scanf("%d",&op);
135 if(op==1){
136 ++n;scanf("%s",s+n);
137 x=ans%26;s[n]=(s[n]-'a'+x)%26+'a';
138 add(s[n]-'a',n);
139 }
140 else{
141 scanf("%d%d",&x,&y);
142 x=(x-1+ans)%n+1;
143 y=(y-1+ans)%n+1;
144 if(x>y)swap(x,y);
145 int l=0,r=y-x+1,mid;
146 while(l+1<r){
147 mid=l+r>>1;
148 if(seg::ask(seg::rt[y],1,A,x+mid-1,y)>=mid)l=mid;
149 else r=mid;
150 }
151 ans=l;printf("%d\n",ans);
152 }
153 }
154 }
View Code