思路:

对于每一个点,它会对自己的一段连续的祖先造成影响.

因此我们就可以用树链剖分维护即可.

(不知道有什么简单写法,我明明没写线段树啊...)

(也许是某种奇怪的单调性,但我不想想这么多了...)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 200010
int pa[N][18];LL d[N][18];
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[200010*20],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[21];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
int head[N],next[N],end[N];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
 
int siz[N],son[N],dep[N];
void Build(int x){
    int Mx=0;siz[x]=1;
    for(int j=head[x];j;j=next[j]){
        dep[end[j]]=dep[x]+1,Build(end[j]);
        if(Mx<siz[end[j]])Mx=siz[end[j]],son[x]=end[j];
        siz[x]+=siz[end[j]];
    }
}
int top[N],pid[N],idp[N],cnt;
void Create(int x,int Top){
    top[x]=Top,idp[pid[x]=++cnt]=x;
    if(son[x])Create(son[x],Top);
    for(int j=head[x];j;j=next[j])if(end[j]!=son[x])Create(end[j],end[j]);
}
 
int ans[N];
inline void cover(int l,int r){
    ans[l]++,ans[r+1]--;
}
 
inline void work(int x,int y){
    while(top[x]!=top[y]){
        if(dep[x]<dep[y])swap(x,y);
        cover(pid[top[x]],pid[x]),x=pa[top[x]][0];
    }
    if(dep[x]<dep[y])swap(x,y);
    cover(pid[y],pid[x]);
}
 
int res[N];
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n;LL l;Fio::Get(n),Fio::Get(l);
    register int i,j;for(i=2;i<=n;++i)Fio::Get(pa[i][0]),Fio::Get(d[i][0]),addedge(pa[i][0],i);
    for(j=1;j<=17;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1],d[i][j]=d[i][j-1]+d[pa[i][j-1]][j-1];
 
    dep[1]=1,Build(1),Create(1,1);
 
    int anc,nowdep;LL nowd;
    for(i=1;i<=n;++i){
        nowd=0,nowdep=dep[i],anc=i;
        for(j=17;j>=0;--j)if(nowdep-(1<<j)>=1&&nowd+d[anc][j]<=l)nowdep-=(1<<j),nowd+=d[anc][j],anc=pa[anc][j];
        work(anc,i);    
    }
 
    int get=0;
    for(i=1;i<=n;++i)res[idp[i]]=get+=ans[i];
 
    for(i=1;i<=n;++i)Fio::print(res[i]);
 
    return Fio::final(),0;
}

思路:这大概也算是后缀自动机裸题了吧.

虽然最小表示法最靠谱,不过我还是懒,于是用map水了一发.好方便啊~`

注意数据范围有一些不靠谱,详情见代码= =

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
#define N 500010
map<int,int>tranc[N<<1];int pa[N<<1],len[N<<1],cnt,root,last;
inline int newnode(int l){
    len[++cnt]=l;return cnt;
}
inline void init(){
    root=last=newnode(0);
}
 
int a[N<<1];
int main(){
    int n;scanf("%d",&n);register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]),a[i+n]=a[i];
    int p,np,q,nq,y;
    for(init(),i=1;i<=n*2;++i){
        np=newnode(len[last]+1);
        for(p=last,y=a[i];tranc[p].find(y)==tranc[p].end();p=pa[p])tranc[p][y]=np;
        if(!p)pa[np]=root;
        else{
            q=tranc[p][y];
            if(len[q]==len[p]+1)pa[np]=q;
            else{
                nq=newnode(len[p]+1),pa[nq]=pa[q],pa[q]=pa[np]=nq;
                tranc[nq]=tranc[q];
                for(;p&&tranc[p].find(y)!=tranc[p].end()&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
            }
        }last=np;
    }
    map<int,int>::iterator it;
    for(i=1,p=root;i<=n;++i){
        if(i>1)putchar(' ');
        it=tranc[p].begin();
        printf("%d",it->first);
        p=tranc[p][it->first];
    }
 
    return 0;
}

思路:

注意到一个关键条件:一个高度为\(n\)的阶梯,必须要正好用\(n\)个矩形拼出来!

考虑阶梯的角落如何放置一个矩形,不难发现的是,这个矩形必须将剩下的两个区域完全分隔开!否则剩下的部分是不可能用\(n-1\)个矩形拼出来的.

于是我们发现答案序列就是卡特兰数.

Python水.

n=int(raw_input())
a=[]
a.append(1)
a.append(1)
for i in range(2,n+1):
    d=0
    for j in range(0,i):
        d+=a[j]*a[i-1-j]
    a.append(d)
print(a[n])

思路:

考虑不存在三角形的情况:也就是说,任意选择三个数,总有一个最大的数不小于剩下两个数的总和.

我们想到一个的数列:斐波那契数列.

那么权值均在题目给定数据范围内的数列有多长?至多有\(log(Max)\)项.

如果超过这些项,就会在两个数之间插入某一个数,那么这三个数就是必定满足三角形条件的.(有点意识流)

总之如果总共有不超过\(log(Max)\)个数暴力判定,否则直接输出\(Y\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int w[N];
 
int pa[N][16],dep[N];
inline void dfs(int x,int fa){
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)dep[end[j]]=dep[x]+1,pa[end[j]][0]=x,dfs(end[j],x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=15;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=15;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
 
int seq[51],id;
 
inline bool judge(int a,int b,int c){
    long long A=a,B=b,C=c;
    return A+B>C&&B+C>A&&A+C>B;
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j,k;for(i=1;i<=n;++i)scanf("%d",&w[i]);
     
    int a,b;for(i=1;i<n;++i)scanf("%d%d",&a,&b),make(a,b);
     
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=15;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
     
    int t;
    while(m--){
        scanf("%d%d%d",&t,&a,&b);
        if(t==0){
            int Lca=lca(a,b),nums=dep[a]+dep[b]-2*dep[Lca]+1;
            if(nums<=40){
                for(id=0;a!=Lca;a=pa[a][0])seq[++id]=w[a];
                for(;b!=Lca;b=pa[b][0])seq[++id]=w[b];
                seq[++id]=w[Lca];
                bool ok=0;
                for(i=1;i<=id;++i)for(j=i+1;j<=id;++j)for(k=j+1;k<=id;++k)if(judge(seq[i],seq[j],seq[k]))ok=1;
                if(ok)puts("Y");else puts("N");
            }else puts("Y");
        }else w[a]=b;
    }
     
    return 0;
}

思路:

令\(x\)是一个可行答案,有\(x^2\%n=1\),即\((x-1)(x+1)=kn(k\in{Z})\).

显然我们可以令\(x-1=k_1n_1,x+1=k_2n_2,k=k_1k_2,n=n_1n_2\).(交换一下也是可以的)

那么我们就可以枚举所有的\(n_1\),看一看他能够表达出的\(x+1\)或是\(x-1\)是不是一个合法答案.我们用一个哈希表来支持插入.最后输出即可.

但是我们发现枚举所有的\(n_1\)(n的约数)显然是要超时的.因此我们只枚举\(n_1\geq{\sqrt{n}}\)的\(n_1\).这样单次枚举的复杂度为\(\sqrt{n}\),而且这样的约数非常少,这样就可以通过了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int mod=(1e5)+7;
struct HashSet{
    int head[mod],v[200010],next[200010],ind;
    void reset(){ind=0,memset(head,-1,sizeof head);}
    void insert(int x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])if(v[j]==x)return;
        v[ind]=x,next[ind]=head[ins],head[ins]=ind++;
    }
}S;
 
int n;
void Solve(int x){
    for(int d=x;d<n-1;d+=x)if((long long)d*(d+2)%n==0)S.insert(d+1);
    for(int d=x;d<=n;d+=x)if(d-2>=1&&(long long)d*(d-2)%n==0)S.insert(d-1);
}
int main(){
    scanf("%d",&n);
    if(n==1)puts("NONE");
    else{
        S.reset(),S.insert(1);
        for(int i=1;i*i<=n;++i)if(n%i==0)Solve(max(i,n/i));
        sort(S.v,S.v+S.ind);
        for(int i=0;i<S.ind;++i)printf("%d\n",S.v[i]);
    }
     
    return 0;
}

思路:

假设我们现在已经求出所有以\(i\)为区间起点的区间的答案.

那么如何求出所有以\(i+1\)为区间起点的区间的答案呢?呢?

考虑现在没有第\(i\)个数了.那么一些区间的答案就会减少.令区间终点为\(j\)的答案为\(f[j]\),在\(i\)后面第一个数值与\(i\)相同的位置为\(next[i]\),那么终点为\([i+1,next[i]-1]\)这段区间内的答案都应该对\(w[i]\)取一个min.

这个非常容易理解.

于是将询问排序,然后用一颗线段树维护标记就行了.时间复杂度\(O(n+m)logn\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
namespace Fio{
    inline int getc(){
#ifndef ONLINE_JUDGE
        static const int L=1<<1;
#else
        static const int L=1<<15;
#endif
        static char buf[L],*readS=buf,*readT=buf;
        if(readS==readT){readT=(readS=buf)+fread(buf,1,L,stdin);if(readS==readT)return EOF;}
        return*readS++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[1500010],*o=buf;
    template<typename T>inline void Print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=stk[i]+48;}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 200010
#define M 200010
int n,m,a[N];
 
struct Query{
    int l,r,lab;
    Query(){}
    Query(int _l,int _r):l(_l),r(_r){}
    bool operator<(const Query&B)const{return l<B.l;}
}Q[M];int res[N];
 
bool vis[N];
 
int ans[N];
struct Node{
    int l,r,c,ans;
}S[N<<2];int cnt;
int Build(int tl,int tr){
    int q=++cnt,mid=(tl+tr)>>1;
    S[q].c=-INF,S[q].ans=ans[mid];
    if(tl==tr)return q;
    S[q].l=Build(tl,mid),S[q].r=Build(mid+1,tr);return q;
}
void Covit(int q,int c){
    S[q].c=(S[q].c==-INF||c<S[q].c)?c:S[q].c,S[q].ans=min(S[q].ans,c);
}
void Push(int q){
    if(S[q].c!=-INF)Covit(S[q].l,S[q].c),Covit(S[q].r,S[q].c),S[q].c=-INF;
}
void Cover(int q,int tl,int tr,int dl,int dr,int c){
    if(dl>dr)return;
    Push(q);
    if(dl<=tl&&tr<=dr){Covit(q,c);return;}
    int mid=(tl+tr)>>1;
    if(dr<=mid)Cover(S[q].l,tl,mid,dl,dr,c);
    else if(dl>mid)Cover(S[q].r,mid+1,tr,dl,dr,c);
    else Cover(S[q].l,tl,mid,dl,mid,c),Cover(S[q].r,mid+1,tr,mid+1,dr,c);
}
int Query(int q,int tl,int tr,int ins){
    if(tl==tr)return S[q].ans;
    Push(q);
    int mid=(tl+tr)>>1;
    if(ins<=mid)return Query(S[q].l,tl,mid,ins);else return Query(S[q].r,mid+1,tr,ins);
}
 
int nxt[N],lst[N];
 
int main(){
    Fio::Get(n),Fio::Get(m);register int i,j;
    for(i=1;i<=n;++i)Fio::Get(a[i]);
    for(i=1;i<=m;++i)Fio::Get(Q[i].l),Fio::Get(Q[i].r),Q[i].lab=i;sort(Q+1,Q+m+1);
     
    int lans=0;
    for(i=1;i<=n;++i){vis[a[i]]=1;for(;vis[lans];++lans);ans[i]=lans;}
 
    for(i=n;i>=1;--i)nxt[i]=lst[a[i]],lst[a[i]]=i;
    for(i=1;i<=n;++i)if(!nxt[i])nxt[i]=n+1;
     
    Build(1,n);
    j=1;
    for(i=1;i<=n;++i){
        for(;j<=n&&Q[j].l==i;++j)res[Q[j].lab]=Query(1,1,n,Q[j].r);
        if(i<n)Cover(1,1,n,i+1,nxt[i]-1,a[i]);
    }
     
    for(i=1;i<=m;++i)Fio::Print(res[i]);
     
    return Fio::final(),0;
}

思路:

首先分数规划是显然的.

其次就是要求长度必须为偶数,我们可以分成两种情况讨论也可以解决.

然后对于每一次二分,我们维护一个前缀和,那么以当前位置为结尾的最大权值和所对应的开头位置的前缀和我们利用一个单调队列维护即可.

关键是输出答案时要输出一个分数或整数!这个坑死爹了.

惨不忍睹地尝试了无数种方法之后.接近崩溃.(尤其是枚举分母一点都不靠谱啊啊啊啊啊啊啊)

终于想到了一种方法,在二分的时候顺便更新答案,最后直接输出.然后就这样水过去了.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
 
typedef long double f2;
typedef long long LL;
 
#define N 100010
int n,l,r,a[N<<1],b[N],q[N],fr,ta;
 
f2 sum[N];LL realsum[N];
 
LL gcd(LL a,LL b){return(!b)?a:gcd(b,a%b);}
 
struct Ans{
    LL x,y;
    Ans(){}
    Ans(LL _x,LL _y):x(_x),y(_y){}
    bool operator<(const Ans&B)const{return x*B.y>y*B.x;}
};
 
inline void upd(Ans&t,int l,int r){
    Ans tmp=Ans(realsum[r]-realsum[l-1],2*(r-l+1));
    if(tmp<t)t=tmp;
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    //freopen("me.out","w",stdout);
#endif
    scanf("%d%d%d",&n,&l,&r);if(l<1)l=1;if(r>n)r=n;
    register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]);for(i=n+1;i<=2*n;++i)a[i]=a[i-n];
     
    l=l%2==0?l:l+1,l>>=1;
    r=r%2==0?r:r-1,r>>=1;
     
    f2 L,R,mid,res=0;
    Ans sav(0,1);
     
    //solve1
    for(i=1;i<=n;++i)b[i]=a[2*i-1]+a[2*i],realsum[i]=realsum[i-1]+b[i];
     
    for(L=0,R=1e9;R-L>1e-10;){
        mid=(L+R)/2;
         
        for(i=1;i<=n;++i)sum[i]=sum[i-1]+b[i]-2*mid;
         
        f2 Max=sum[l];upd(sav,1,l);
        for(fr=ta=0,i=l+1;i<=n;++i){
            if(i<=r)Max=max(Max,sum[i]),upd(sav,1,i);
            while(fr^ta&&sum[q[ta-1]]>sum[i-l])--ta;q[ta++]=i-l;
            while(fr^ta&&q[fr]<i-r)++fr;if(fr^ta)Max=max(Max,sum[i]-sum[q[fr]]),upd(sav,q[fr]+1,i);
        }
         
        if(Max>=0)L=mid;else R=mid;
    }res=max(res,L);
     
    //solve2
    for(i=1;i<n;++i)b[i]=a[2*i]+a[2*i+1];b[n]=a[2*n]+a[1];
    for(i=1;i<=n;++i)realsum[i]=realsum[i-1]+b[i];
     
    for(L=0,R=1e9;R-L>1e-10;){
        mid=(L+R)/2;
         
        for(i=1;i<=n;++i)sum[i]=sum[i-1]+b[i]-2*mid;
         
        f2 Max=sum[l];upd(sav,1,l);
        for(fr=ta=0,i=l+1;i<=n;++i){
            if(i<=r)Max=max(Max,sum[i]),upd(sav,1,i);
            while(fr^ta&&sum[q[ta-1]]>sum[i-l])--ta;q[ta++]=i-l;
            while(fr^ta&&q[fr]<i-r)++fr;if(fr^ta)Max=max(Max,sum[i]-sum[q[fr]]),upd(sav,q[fr]+1,i);
        }
     
        if(Max>=0)L=mid;else R=mid;
    }res=max(res,L);
     
     
    LL ansx=sav.x,ansy=sav.y,Gcd=gcd(ansx,ansy);ansx/=Gcd,ansy/=Gcd;
#ifndef ONLINE_JUDGE
    if(ansy==1)printf("%I64d",ansx);else printf("%I64d/%I64d",ansx,ansy);
#else
    if(ansy==1)printf("%lld",ansx);else printf("%lld/%lld",ansx,ansy);
#endif
     
    return 0;
}

思路:

首先平衡点貌似是平面上这些点的广义费马点.广义费马点就是到所有点的距离与权值的乘积之和最小的一个点.

(这为什么我并不知道)

不过有了这个就可以用模拟退火随便玩了.

(你们感受一下代码长度)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define N 10010
int n;f2 x[N],y[N],w[N];
 
f2 sqr(f2 dx){return dx*dx;}
f2 calc(f2 dx,f2 dy){
    f2 res=0;
    for(int i=1;i<=n;++i)res+=sqrt(sqr(dx-x[i])+sqr(dy-y[i]))*w[i];
    return res;
}
 
f2 get(){
    int d=rand()%1000;
    return (rand()&1?-1:1)*(d/1000.0);
}
 
int main(){
    scanf("%d",&n);register int i,j;
     
    f2 addx=0,addy=0;for(i=1;i<=n;++i)scanf("%lf%lf%lf",&x[i],&y[i],&w[i]),addx+=x[i],addy+=y[i];
    addx/=n,addy/=n;
     
    f2 ansx,ansy,ans;
    f2 nowx=addx,nowy=addy,nowans=calc(nowx,nowy),nxtx,nxty,nxtans;
    ans=nowans,ansx=nowx,ansy=nowy;
     
    f2 T=1e6;
    for(;T>1e-3;T*=0.993){
        nxtans=calc(nxtx=nowx+T*get(),nxty=nowy+T*get());
        if(nxtans<ans)ans=nxtans,ansx=nxtx,ansy=nxty;
        if(nxtans<nowans||exp((nowans-nxtans)/T)>fabs(get()))nowans=nxtans,nowx=nxtx,nowy=nxty;
    }
    for(i=1;i<=1000;++i){
        nxtans=calc(nxtx=ansx+T*get(),nxty=ansy+T*get());
        if(nxtans<ans)ans=nxtans,ansx=nxtx,ansy=nxty;
    }
     
    printf("%.3lf %.3lf",ansx,ansy);
     
    return 0;
}

思路:

首先我们需要知道欧拉函数的计算方法:

\[n=p_1^{q_1}p_2^{q_2}...p_m^{q_m}\rightarrow\phi(n)=n\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}...\frac{p_m-1}{p_m}\]

\[\phi(n)=p_1^{q_1}\frac{p_1-1}{p_1}p_2^{q_2}\frac{p_2-1}{p_2}...p_m^{q_m}\frac{p_m-1}{p_m}\]

这证明我们可以将所有的质因数分开考虑.

我们对于所有质因数计算其贡献,然后乘到一起.(这东西维护一个前缀和就行了)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
#define N 10000010
int p[N/10],ins[N],cnt;bool notp[N];vector<int>v[N/10];
inline void pre(){
    register int i,j;
    for(i=2;i<=10000000;++i){
        if(!notp[i])p[++cnt]=i,ins[i]=cnt;
        for(j=1;j<=cnt&&i*p[j]<=10000000;++j){
            notp[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
 
static const int mod=(1e9)+7;
inline int ksm(int x,int y){
    int t=x,res=1;for(;y;y>>=1,t=(long long)t*t%mod)if(y&1)res=(long long)res*t%mod;return res;
}
inline int inv(int x){
    return ksm(x,mod-2);
}
inline void inc(int&x,int y){
    if((x+=y)>=mod)x-=mod;
}
 
int seq[1000010],num;vector<int>vv[1000010];
 
int pref[40];
 
int main(){ 
    pre();
     
    int n;scanf("%d",&n);register int i,j,k;
    int x,nowadd;
    while(n--){
        scanf("%d",&x);if(x==1)continue;
        for(i=1;i<=cnt&&p[i]*p[i]<=x;++i){
            nowadd=0;while(x%p[i]==0)++nowadd,x/=p[i];
            if(nowadd)v[i].push_back(nowadd);
        }if(x)v[ins[x]].push_back(1);
    }
     
    for(i=1;i<=cnt;++i)if((int)v[i].size()!=0){
        seq[++num]=p[i];
        for(j=0;j<(int)v[i].size();++j)vv[num].push_back(v[i][j]);
    }
     
    if(num==0)puts("1");
    else{
        int res=1,Mx,mi,tans;
        for(k=1;k<=num;++k){
            for(Mx=0,i=0;i<vv[k].size();++i)Mx=max(Mx,vv[k][i]);
            for(pref[0]=1,mi=seq[k],i=1;i<=Mx;++i,mi=(long long)mi*seq[k]%mod)inc(pref[i]=pref[i-1],mi);
            for(tans=1,i=0;i<vv[k].size();++i)tans=(long long)tans*pref[vv[k][i]]%mod;
            tans=(long long)(tans+mod-1)*(seq[k]-1)%mod;
            tans=(long long)tans*inv(seq[k])%mod;
            res=(long long)res*(tans+1)%mod;
        }
        printf("%d",res);
    }
     
    return 0;
}

思路:

首先考虑如果一个串固定时,如何求出最多的出现次数.

当模式串存在覆盖关系时,很显然可以舍弃掉一些.那么现在所有的串之间都不存在覆盖关系.

那么我们可以从前向后扫描,如果出现一个完整的模式串,答案加1,同时将指针移到下一个位置继续刚才的操作.

由于不存在覆盖关系,这样的贪心是很显然的,不信的话可以自己画图看看.

考虑将模式串建成AC自动机.令\(P[i][j]\)表示串长为\(i\),现在处于AC自动机上的节点\(j\)上的概率.这个很容易用矩阵乘法搞定.

那么我们的答案是是什么呢?

考虑从某个节点转移到某个完全包含某个模式串的节点,那么此时答案+1,同时状态回到根节点.我们只要在矩阵中加一维计数器来搞就行了.

其实没说什么= =  不懂自己看代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int ch[80][26],fail[80],end[80],cnt,q[80],fr,ta;
 
char s[20],sav[6][20];int len[6];bool covered[6];
 
typedef long double f4;
 
struct Matrix{
    f4 d[81][81];int w,h;
    Matrix(){}
    Matrix(int _w,int _h):w(_w),h(_h){}
     
    void operator*=(const Matrix&B){
        register int i,j,k;
        Matrix res(w,B.h);
        for(i=0;i<res.w;++i)for(j=0;j<res.h;++j){
            res.d[i][j]=0;for(k=0;k<h;++k)res.d[i][j]+=d[i][k]*B.d[k][j];
        }
        *this=res;
    }
};
 
bool cover(int a,int b){
    if(len[a]<len[b])return 0;
    register int i,j;
    for(i=1;i+len[b]-1<=len[a];++i){
        bool ok=1;
        for(j=1;j<=len[b];++j)if(sav[a][i+j-1]!=sav[b][j])ok=0;
        if(ok)return 1;
    }
    return 0;
}
 
int main(){
    int n,L,k;scanf("%d%d%d",&n,&L,&k);register int i,j;
     
    for(i=1;i<=n;++i)scanf("%s",sav[i]+1),len[i]=strlen(sav[i]+1);
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(cover(i,j))covered[i]=1;
     
    bool allcovered=1;for(i=1;i<=n;++i)if(!covered[i])allcovered=0;
    if(allcovered)covered[1]=0;
     
    int p,y;
    for(i=1;i<=n;++i)if(!covered[i]){
        p=0;for(j=1;j<=len[i];++j){if(!ch[p][y=sav[i][j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
        end[p]=1;
    }
     
    for(j=0;j<k;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<k;++j){
            if((v=ch[u][j])){
                q[ta++]=v;
                for(r=fail[u];r&&!ch[r][j];r=fail[r]);
                end[v]|=end[fail[v]=ch[r][j]];
            }else ch[u][j]=ch[fail[u]][j];
        }
    }
     
    Matrix res(1,cnt+2);res.d[0][0]=1;
     
    Matrix add(cnt+2,cnt+2);add.d[cnt+1][cnt+1]=1;
    for(i=0;i<=cnt;++i){
        for(j=0;j<k;++j){
            if(end[ch[i][j]])add.d[i][cnt+1]+=(f4)1/k,add.d[i][0]+=(f4)1/k;
            else add.d[i][ch[i][j]]+=(f4)1/k;
        }
    }
     
    for(;L;L>>=1,add*=add)if(L&1)res*=add;
     
    double output=res.d[0][cnt+1];
    printf("%.6lf",output);
     
     
    return 0;
}