【题解】Luogu P5337 [TJOI2019]甲苯先生的字符串

女爷i 2021-10-26 16:31 265阅读 0赞

### [原题传送门][Link 1] ###

#### 我们设计一个\\(26\*26\\)的矩阵\\(A\\)表示\\(a~z\\)和\\(a~z\\)是否能够相邻，这个矩阵珂以由\\(s1\\)得出。答案显然是矩阵\\(A^\{len\_\{s2\}-1\}\\)的所有元素之和，矩阵快速幂即可 ####

#include <bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std; inline void write(register int x) { if(!x)putchar('0');if(x<0)x=-x,putchar('-'); static int sta[20];register int tot=0; while(x)sta[tot++]=x%10,x/=10; while(tot)putchar(sta[--tot]+48); } struct mat{ int a[26][26]; inline mat() { memset(a,0,sizeof(a)); } inline mat operator*(const mat&b)const{ mat c; for(register int i=0;i<26;++i) for(register int j=0;j<26;++j) for(register int k=0;k<26;++k) c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j])%mod; return c; } }s; inline mat fastpow(register mat a,register ll b) { mat ret; for(register int i=0;i<26;++i) ret.a[i][i]=1; while(b) { if(b&1) ret=ret*a; a=a*a; b>>=1; } return ret; } ll n,ans; char str[100005]; int main() { scanf("%lld%s",&n,str+1); int len=strlen(str+1); for(register int i=0;i<26;++i) for(register int j=0;j<26;++j) s.a[i][j]=1; for(register int i=1;i<len;++i) s.a[str[i]-'a'][str[i+1]-'a']=0; mat res=fastpow(s,n-1); for(register int i=0;i<26;++i) for(register int j=0;j<26;++j) ans=(ans+res.a[i][j])%mod; write(ans); return 0; }

转载于:https://www.cnblogs.com/yzhang-rp-inf/p/10957741.html

[Link 1]: https://www.luogu.org/problemnew/show/P5337

发表评论取消回复

表情：

评论列表（有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读

相关题解 luogu P1850 【换教室】

题解 luogu P1850 【换教室】时间：2019.8.6 一晚上（约 3.5h 写完）题目描述对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际

Dear 丶/ 2023年10月09日 09:42/ 0 赞/ 43 阅读

相关题解 luogu P5021 【赛道修建】

题解 luogu P5021 【赛道修建】时间：2019.8.9 20:40 时间：2019.8.12 题目描述 C 城将要举办一系列的赛车比赛。在比赛前，需

今天药忘吃喽~/ 2023年10月09日 09:41/ 0 赞/ 33 阅读

相关 luogu P1311 选择客栈题解

\\(luogu\\) P1311 选择客栈题解 [题目链接][Link 1] 看到这道题目首先很茫然，一看统计方案数，肯定要什么数论或者数学知识吧，然后就打了个暴力

小咪咪/ 2023年06月01日 15:54/ 0 赞/ 10 阅读

相关 [TJOI2019]甲苯先生的字符串——矩阵乘法+递推

题目链接： [\[TJOI2019\]甲苯先生的字符串][TJOI2019] 我们用一个$26\26$的$01$矩阵记录任意两个字符是否能相邻。设$f\[i\

电玩女神/ 2022年01月13日 04:27/ 0 赞/ 235 阅读

相关 luogu P5342 [TJOI2019]甲苯先生的线段树

[传送门][Link 1] > 你个好好的省选怎么可以出CF原题啊,你们这个题害人不浅啊,这样子出题像极了cxk,说到cxk,我又想起了他是NBA形象大使,跟我是西游文化大使

刺骨的言语ヽ痛彻心扉/ 2021年12月13日 04:38/ 0 赞/ 186 阅读

相关【题解】Luogu P1083 借教室

用差分数组(b\[i\])存每天教室的使用情况所以当对区间操作时，其实可以转化成对b数组操作： b[s[i]]+=d[i]; b[t[i]+1]-=d[i

亦凉/ 2021年11月17日 15:02/ 0 赞/ 254 阅读

相关【题解】Luogu P5468 [NOI2019]回家路线

[原题传送门][Link 1] 前置芝士：斜率优化不会的可以去[杜神博客][Link 2]学这道题我考场上只会拆点跑最短路的70pts做法后来回家后发

水深无声/ 2021年10月30日 03:22/ 0 赞/ 339 阅读

相关【题解】Luogu P5337 [TJOI2019]甲苯先生的字符串

[原题传送门][Link 1] 我们设计一个\\(26\26\\)的矩阵\\(A\\)表示\\(a~z\\)和\\(a~z\\)是否能够相邻，这个矩阵珂以由\\(s1\

女爷i/ 2021年10月26日 16:31/ 0 赞/ 266 阅读

相关【题解】Luogu P5471 [NOI2019]弹跳

[原题传送门][Link 1] 先考虑部分分做法： subtask1：暴力\\(O(nm)\\)枚举，跑最短路 subtask2: 吧一行的点压到vecto

逃离我推掉我的手/ 2021年10月20日 00:20/ 0 赞/ 318 阅读

相关【题解】Luogu P2257 YY的GCD

[原题传送门][Link 1] 这题需要运用[莫比乌斯反演(懵逼钨丝繁衍)][Link 2] 显然题目的答案就是\\\[ Ans=\\sum\_\{i=1\}^N

た入场券/ 2021年10月01日 06:44/ 0 赞/ 281 阅读