[bzoj5508]甲苯先生的字符串

发布时间：2020-12-16 10:48:39 所属栏目：百科来源：网络整理

导读：首先定义状态 f[i][j] 表示长度为 i 的串以 j 为结尾有多少符合条件的串，发现$f[i][j]=sum f[i-1][k]$ (j 和 k 可以相邻 ) ，这个用矩阵乘法优化一下即可。 1 #includebits/stdc++.h 2 using namespace std; 3 #define ll long long 4 #define mod 1000000

首先定义状态f[i][j]表示长度为i的串以j为结尾有多少符合条件的串，发现$f[i][j]=sum f[i-1][k]$(j和k可以相邻)，这个用矩阵乘法优化一下即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define mod 1000000007
 5 struct ji{
 6     ll a[31][31];
 7 }a,b,c;
 8 ll n,ans;
 9 char s[100001];
10 ji cheng(ji a,ji b){
11     memset(c.a,0,sizeof(c.a));
12     for(int i=0;i<26;i++)
13         for(int j=0;j<26;j++)
14             if (a.a[i][j])
15                 for(int k=0;k<26;k++)c.a[i][k]=(c.a[i][k]+a.a[i][j]*b.a[j][k])%mod;
16     return c;
17 }
18 int main(){
19     scanf("%lld%s",&n,s);
20     for(int i=0;i<26;i++)
21         for(int j=0;j<26;j++)a.a[i][j]=1;
22     for(int i=0;s[i+1];i++)a.a[s[i]-‘a‘][s[i+1]-‘a‘]=0;
23     for(int i=0;i<26;i++)b.a[i][i]=1;
24     for(n--;n;n>>=1){
25         if (n&1)b=cheng(b,a);
26         a=cheng(a,a);
27     }
28     for(int i=0;i<26;i++)
29         for(int j=0;j<26;j++)ans=(ans+b.a[i][j])%mod;
30     printf("%lld",ans);
31 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!