转载

$Luogu$ $P5337$ $[TJOI2019]$ 甲苯先生的字符串

链接

背景

\(CCF\) \(NOI\) \(2019\) 天津市代表队选拔 \(Day1\) \(T1\)\(Luogu\) \(P5337/LOJ3104\)

题意

咕咕咕

解法

细节

代码

\(View\) \(Code\)

#include<bits/stdc++.h> using namespace std; inline long long readl() { long long ret=0; int f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int len; long long n,ans; char s[100005]; struct mat { long long m[26][26]; }; const int mod=1e9+7; mat mul(mat a,mat b) { mat ret; for(register int i=0;i<26;i++) for(register int j=0;j<26;j++) ret.m[i][j]=0; for(register int i=0;i<26;i++) for(register int j=0;j<26;j++) for(register int k=0;k<26;k++) ret.m[i][j]=(ret.m[i][j]+a.m[i][k]*b.m[k][j])%mod; for(register int i=0;i<26;i++) for(register int j=0;j<26;j++) ret.m[i][j]%=mod; return ret; } mat matpow(mat a,long long k) { mat ret; for(register int i=0;i<26;i++) for(register int j=0;j<26;j++) ret.m[i][j]=(i==j); while(k) { if(k&1) ret=mul(ret,a); a=mul(a,a); k/=2; } return ret; } int main() { n=readl(); scanf("%s",s); len=strlen(s); mat a; for(register int i=0;i<26;i++) for(register int j=0;j<26;j++) a.m[i][j]=1; for(register int i=1;i<len;i++) a.m[s[i-1]-'a'][s[i]-'a']=0; a=matpow(a,n-1); for(register int i=0;i<26;i++) for(register int j=0;j<26;j++) ans+=a.m[i][j]; printf("%lld\n",ans%mod); }

转载于:https://www.cnblogs.com/Peter0701/p/11393660.html

正文到此结束
本文目录