[ctsc2006]歌唱王国

最近在啃《混凝土数学》……被干翻了……
然后利用了一下新学的东西……写了一下这道题……
吐槽标题——singleland真的不是单身大陆么……(不知道原题面是怎么样的……但bzoj上就是single land)

鉴于我还要准备会考……期末考之类的东西……暂时就不用latex码公式了…… 啥时候有时间了填这个好了

singleland.cpp
#include<cstdio>
using namespace std;
const int mod=10000;
#define N 200000
int n,t,a[N],nex[N],m;
int mod_pow(int x,int y)
{
    int res=1;x%=mod;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1)res=res*x%mod;
    return res;
}
int main(){
    scanf("%d%d",&n,&t);
    while(t--)
    {
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            scanf("%d",&a[i]);
        //Kmp

        nex[1]=0;
        for(int i=1;i<=m;i++)
        {
            int j=nex[i];
            while(j&&a[j+1]!=a[i+1])j=nex[j];
            if(a[j+1]!=a[i+1])
                nex[i+1]=0;
            else nex[i+1]=j+1;
        }
        int ans=0;
        for(int i=m;i;i=nex[i])
            ans=(ans+mod_pow(n,i))%mod;
        printf("%04d\n",ans);
    }
}

Comments

comments powered by Disqus