列表

详情

NC25168. 311045 / 密涅瓦的谜题

描述

威廉·密涅瓦？图书室里，三个人围着一张桌子念叨着这个名字，并寻找着什么。
终于，在一本印有猫头鹰的大书中，他们找到了一个字符串。这个字符串 s 仅由 26 个小写拉丁字母构成，长度为 n 。看似无意义的字母的拼接，会有什么意义呢？诺曼萌生了一个想法。他先从这个大字符串 s 中选择一个子串 t_1 ，将其抄写在一张纸上；再选择 s 的一个子串 t_2 ，将其紧接着抄写在 t_1 后。如此做若干次，直到总共挑选出了恰好 m 个子串 ，它们首尾依次相接能得到另一个大字符串 t 。诺曼想知道，对于一个给定的 m ，最终能得到多少种可能的字符串 t ？
子串是指一段连续的字符；所选择的子串 在位置上可以有重合；可以选择空串，最后得到的字符串也可以是空串；两个字符串 p, q 被视为不同当且仅当两字符串长度不同，或者存在至少一个下标 ，使得 p 的第 i 个字符与 q 的第 i 个字符不同。

输入描述

输入的第一行包含一个字符串 s 。即在书中找到的大字符串。
第二行包含一个正整数 q ，表示有 q 次询问。
接下去 q 行，每行一个正整数 m ，表示一次询问。m 的意义如题面中所述。

输出描述

输出包含 q 行，每行一个整数，表示对应的一次询问的答案在模  意义下的值。

示例1

输入: 

aab
3
1
2
3

输出: 

6
25
96

说明:

当 m=1 时，可能的字符串有 "", "a", "aa", "aab", "ab", "b" 。共 6 种。
当 m=2 时，可能的字符串有 "aba", "aabaab", "aab", "abb", "aaaa", "abaa", "ba" 等等；但不可能是 "bbb", "aaaaa", "aabaabaab", "baaa" 等字符串。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 974ms, 内存消耗: 68584K, 提交时间: 2019-05-24 17:12:43 

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+5;
const int A=26;
const int mod=1e9+7;
int n,q,tot=1,lst=1,tr[N][A],fa[N],len[N],t[N],a[N],dp[N][A+1],foo[N][A+1],bar[N][A+1];
char str[N];
struct mat{
    int s[A+1][A+1];
    mat(){memset(s,0,sizeof(s));}
    int *operator [](int x){return s[x];}
}S,T;
mat operator * (mat a,mat b){
    mat c;
    for(int i=0;i<=A;++i)
        for(int j=0;j<=A;++j)
            for(int k=0;k<=A;++k)
                c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%mod;
    return c;
}
mat fastpow(mat a,int b){
    mat c;for(int i=0;i<=A;++i)c[i][i]=1;
    while(b){if(b&1)c=c*a;a=a*a;b>>=1;}
    return c;
}
void extend(int c){
    int v=lst,u=++tot;len[u]=len[v]+1;lst=u;
    while(v&&!tr[v][c])tr[v][c]=u,v=fa[v];
    if(!v)fa[u]=1;
    else{
        int x=tr[v][c];
        if(len[x]==len[v]+1)fa[u]=x;
        else{
            int y=++tot;
            memcpy(tr[y],tr[x],A<<2);
            fa[y]=fa[x];fa[x]=fa[u]=y;len[y]=len[v]+1;
            while(v&&tr[v][c]==x)tr[v][c]=y,v=fa[v];
        }
    }
}
int main(){
    scanf("%s",str+1);n=strlen(str+1);
    for(int i=n;i;--i)extend(str[i]-'a');
    for(int i=1;i<=tot;++i)t[i]=0;
    for(int i=1;i<=tot;++i)++t[len[i]];
    for(int i=1;i<=tot;++i)t[i]+=t[i-1];
    for(int i=1;i<=tot;++i)a[t[len[i]]--]=i;
    for(int i=tot;i;--i){
        int x=a[i];dp[x][A]=1;
        for(int j=0;j<A;++j)
            if(tr[x][j])
                for(int k=0;k<=A;++k)
                    dp[x][k]=(dp[x][k]+dp[tr[x][j]][k])%mod;
            else ++dp[x][j];
    }
    for(int i=0;i<A;++i)if(tr[1][i])for(int j=0;j<=A;++j)S[j][i]=dp[tr[1][i]][j];
    S[A][A]=1;T=fastpow(S,100001);foo[0][A]=1;
    for(int i=1;i<=100000;++i)
        for(int j=0;j<=A;++j)
            for(int k=0;k<=A;++k)
                foo[i][k]=(foo[i][k]+1ll*foo[i-1][j]*S[j][k])%mod;
    for(int i=0;i<=A;++i)bar[0][i]=1;
    for(int i=1;i<=100000;++i)
        for(int j=0;j<=A;++j)
            for(int k=0;k<=A;++k)
                bar[i][j]=(bar[i][j]+1ll*bar[i-1][k]*T[j][k])%mod;
    scanf("%d",&q);while(q--){
        long long m;scanf("%lld",&m);int ans=0;
        for(int i=0;i<=A;++i)ans=(ans+1ll*foo[m%100001][i]*bar[m/100001][i])%mod;
        printf("%d\n",ans);
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 732ms, 内存消耗: 67168K, 提交时间: 2019-05-23 21:13:19 

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+5;
const int A=26;
const int mod=1e9+7;
int n,q,tot=1,lst=1,tr[N][A],fa[N],len[N],t[N],a[N],dp[N][A+1],foo[N][A+1],bar[N][A+1];
char str[N];
struct mat{
	int s[A+1][A+1];
	mat(){memset(s,0,sizeof(s));}
	int *operator [](int x){return s[x];}
}S,T;
mat operator * (mat a,mat b){
	mat c;
	for(int i=0;i<=A;++i)
		for(int j=0;j<=A;++j)
			for(int k=0;k<=A;++k)
				c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%mod;
	return c;
}
mat fastpow(mat a,int b){
	mat c;for(int i=0;i<=A;++i)c[i][i]=1;
	while(b){if(b&1)c=c*a;a=a*a;b>>=1;}
	return c;
}
void extend(int c){
	int v=lst,u=++tot;len[u]=len[v]+1;lst=u;
	while(v&&!tr[v][c])tr[v][c]=u,v=fa[v];
	if(!v)fa[u]=1;
	else{
		int x=tr[v][c];
		if(len[x]==len[v]+1)fa[u]=x;
		else{
			int y=++tot;
			memcpy(tr[y],tr[x],A<<2);
			fa[y]=fa[x];fa[x]=fa[u]=y;len[y]=len[v]+1;
			while(v&&tr[v][c]==x)tr[v][c]=y,v=fa[v];
		}
	}
}
int main(){
	scanf("%s",str+1);n=strlen(str+1);
	for(int i=n;i;--i)extend(str[i]-'a');
	for(int i=1;i<=tot;++i)t[i]=0;
	for(int i=1;i<=tot;++i)++t[len[i]];
	for(int i=1;i<=tot;++i)t[i]+=t[i-1];
	for(int i=1;i<=tot;++i)a[t[len[i]]--]=i;
	for(int i=tot;i;--i){
		int x=a[i];dp[x][A]=1;
		for(int j=0;j<A;++j)
			if(tr[x][j])
				for(int k=0;k<=A;++k)
					dp[x][k]=(dp[x][k]+dp[tr[x][j]][k])%mod;
			else ++dp[x][j];
	}
	for(int i=0;i<A;++i)if(tr[1][i])for(int j=0;j<=A;++j)S[j][i]=dp[tr[1][i]][j];
	S[A][A]=1;T=fastpow(S,100001);foo[0][A]=1;
	for(int i=1;i<=100000;++i)
		for(int j=0;j<=A;++j)
			for(int k=0;k<=A;++k)
				foo[i][k]=(foo[i][k]+1ll*foo[i-1][j]*S[j][k])%mod;
	for(int i=0;i<=A;++i)bar[0][i]=1;
	for(int i=1;i<=100000;++i)
		for(int j=0;j<=A;++j)
			for(int k=0;k<=A;++k)
				bar[i][j]=(bar[i][j]+1ll*bar[i-1][k]*T[j][k])%mod;
	scanf("%d",&q);while(q--){
		long long m;scanf("%lld",&m);int ans=0;
		for(int i=0;i<=A;++i)ans=(ans+1ll*foo[m%100001][i]*bar[m/100001][i])%mod;
		printf("%d\n",ans);
	}
	return 0;
}

上一题

© 2024 nowcoder.com