期望得分：20+40+100=160
实际得分：20+20+100=140
破题关键：
f（i）=i
证明：设[1,i]中与i互质的数分别为a1，a2……aφ(i)
那么 i-a1，i-a2，…… i-aφ(i) 也与i互质
所以 Σ ai = i*φ(i)- Σ ai
所以 Σ ai = i*φ(i)/2
所以 f（i）Σai / φ(i) * 2 = i
问题转化为 求 Σ i^k
用拉格朗日差值法
我是真没看懂
题解：
std：
#include <cstring> #include <ctime> #include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; const int Mod=998244353; const int MAXK=1000000; int power(int x,int k) { int ret=1; while (k) { if (k&1) ret=1LL*ret*x%Mod; x=1LL*x*x%Mod; k>>=1; } return ret; } int k; int f[MAXK+10]; int pre[MAXK+10],suf[MAXK+10]; int jc[MAXK+10],K[MAXK+10]; int cnt(int n) { if (n==0) return 0; int ans=0; if (n<=k+10 || n<=MAXK) { for (int i=1;i<=n;i++) ans=(K[i]+ans)%Mod; } else { pre[0]=1; for (int i=1;i<=k+2;i++) pre[i]=1LL*pre[i-1]*(n-i)%Mod; suf[k+3]=1; for (int i=k+2;i>=1;i--) suf[i]=1LL*suf[i+1]*(n-i)%Mod; int l=k+1,r=0,flag=((k+1)&1)?(-1):(1); for (int i=1;i<=k+2;i++) { int s=1LL*pre[i-1]*suf[i+1]%Mod,m=1LL*(flag*jc[l]+Mod)*jc[r]%Mod; ans=(1LL*f[i]*s%Mod*power(m,Mod-2)%Mod+ans)%Mod; l--; r++; flag*=-1; } } ans=((ans+K[2])%Mod-1+Mod)%Mod; return ans; } int L,R; void init() { cin>>L>>R>>k; for (int i=1;i<=MAXK+5;i++) K[i]=power(i,k); jc[0]=1; for (int i=1;i<=k+2;i++) jc[i]=1LL*jc[i-1]*i%Mod; for (int i=1;i<=k+2;i++) f[i]=(f[i-1]+K[i])%Mod; cout<<(cnt(R)-cnt(L-1)+Mod)%Mod; return ; } int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); init(); fclose(stdin); fclose(stdout); //fprintf(stderr,"%.3lf ",1.0*clock()/(1.0*CLOCKS_PER_SEC)); return 0; }
令b[i]=a[i]-k
令sum[i] 表示 b[i] 的前缀和
则题目转化为
最大化r-l，l r 满足 sum[r]-sum[l]>=0
令m[i] 表示r=i时，最优的l
那么枚举r，ans=max（r-m[r]）
若i<j 且 sum[i]<=sum[j] 那么 i-m[i] 一定不会成为最优解
因为此时 m[i]~j 更优
去除冗余的i之后，剩余的sum[i] 单调递减
维护一个单调栈，栈内sum[i]单调递减
因为随着r的左移，l不会右移
所以维护两个指针l，r
r从n枚举到1，
在栈中找到第一个>sum[r]的sum[k]
那么l=栈中第k+1的元素
因为k以及k之前的位置，在栈中的都比sum[r]大
不在栈中的，因为栈是一个单调递减的栈，所以他们的sum也比sum[r]大
#include<cstdio> #include<iostream> #include<algorithm> #define N 1000002 using namespace std; int a[N]; long long b[N]; int st[N],top; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar();} } int main() { freopen("blocks.in","r",stdin); freopen("blocks.out","w",stdout); int n,m,k,ans; read(n); read(m); for(int i=1;i<=n;i++) read(a[i]); while(m--) { read(k); for(int i=1;i<=n;i++) b[i]=a[i]-k+b[i-1]; top=1; ans=0; for(int i=1;i<=n;i++) if(!top || b[i]<b[st[top]]) st[++top]=i; for(int i=n;i;i--) { while(top && b[st[top]]<=b[i]) top--; ans=max(ans,i-st[top+1]); } printf("%d ",ans); } }
hash+二分
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define N 50001 #define M 100001 #define S 1000001 #define mod 1500007 char s[10001]; int tot; int has[S],bit[10001]; int len[N+M],R[N+M]; int w[11]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } void cal(int i) { len[i]=strlen(s+1); R[i]=tot+len[i]; has[tot+1]=s[1]-'a'; for(int j=2;j<=len[i];j++) has[tot+j]=(has[tot+j-1]*26+s[j]-'a')%mod; tot+=len[i]; } int gethash(int i,int l,int r,int length) { if(R[i]-len[i]+1==l) return has[r]; return (has[r]-1ll*has[l-1]*bit[length]%mod+mod)%mod; } int main() { freopen("biology.in","r",stdin); freopen("biology.out","w",stdout); int n,m; read(n); read(m); bit[0]=1; for(int i=1;i<=10000;i++) bit[i]=bit[i-1]*26%mod; for(int i=1;i<=n;i++) { scanf("%s",s+1); cal(i); } int ty,y,mi; int l,r,mid,ans; int st; bool ok; while(m--) { read(ty); if(ty==1) { scanf("%s",s+1); cal(++n); } else { read(y); mi=M; for(int i=1;i<=y;i++) read(w[i]),mi=min(len[w[i]],mi); l=0,r=mi,ans=0; while(l<=r) { mid=l+r>>1; st=gethash(w[1],R[w[1]]-mid+1,R[w[1]],mid); ok=true; for(int i=2;i<=y && ok;i++) if(gethash(w[i],R[w[i]]-mid+1,R[w[i]],mid)!=st) ok=false; if(ok) ans=mid,l=mid+1; else r=mid-1; } printf("%d ",ans); } } }
std思路：
后缀倒过来转变成前缀，然后求trie树上的LCA的深度就是答案
std：
#include <cstring> #include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; int read() { int ret=0; char c=getchar(); while (c<'0' || c>'9') c=getchar(); while (c>='0' && c<='9') { ret=ret*10+c-'0'; c=getchar(); } return ret; } const int MAXLOG=20,MAXT=1000000; const int MAXN=100000,MAXL=10000; int LOG[MAXL+10]; int n,m,len,cnt; int pos[MAXN+10]; char last[MAXN+10]; struct Trie { int s[26]; int f[MAXLOG+10]; int dep; }tr[MAXT+10]; char str[MAXL+10]; void insert(int x) { last[x]=str[len-1]; int now=1; for (int i=len-1;i>=0;i--) { int id=str[i]-'a'; if (!tr[now].s[id]) { tr[now].s[id]=++cnt; tr[cnt].f[0]=now; tr[cnt].dep=tr[now].dep+1; for (int i=1;i<=MAXLOG;i++) { tr[cnt].f[i]=tr[tr[cnt].f[i-1]].f[i-1]; if (tr[cnt].f[i]==0) break; } } now=tr[now].s[id]; } pos[x]=now; return ; } int up(int x,int step) { while (step) { int up=LOG[step]; x=tr[x].f[up]; step-=(1<<up); } return x; } int LCA(int x,int y) { if (tr[x].dep>tr[y].dep) x=up(x,tr[x].dep-tr[y].dep); else y=up(y,tr[y].dep-tr[x].dep); if (x==0 || y==0) puts("WTF??"); int k=LOG[tr[x].dep]; while (x!=y) { while (k>=0 && tr[x].f[k]==tr[y].f[k]) k--; if (k==-1) return tr[x].f[0]; x=tr[x].f[k]; y=tr[y].f[k]; } return x; } void init() { for (int i=1,now=-1,next=1;i<=MAXL;i++) { if (i==next) { now++; next<<=1; } LOG[i]=now; } n=read(),m=read(); cnt=1; int sum=0; for (int i=1;i<=n;i++) { scanf(" %s",str); len=strlen(str); sum+=len; insert(i); } while (m--) { int ty=read(); if (ty==1) { scanf("%s",str); len=strlen(str); insert(++n); } else { int T=read(),ans=0; while (T--) { int x=read(); //putchar(last[x]); putchar(' '); if (ans==0) ans=pos[x]; else ans=LCA(ans,pos[x]); } printf("%d ",tr[ans].dep); } } return ; } int main() { freopen("biology.in","r",stdin); freopen("biology.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }