HDU 5318 The Goddess Of The Moon(递推+矩阵优化)
分类：DP
题目链接：传送门
题意：
相当于有一个长度为m的路，我们有n种砖，每种砖被表示为一个字符串，一个长度大于等于2的后缀等于
另一个字符串的前缀那么那一块砖就可以放在这块砖的后面。
分析：
这个就是常见的铺砖的那个模型变化而来的，但是这题的递推关系需要根据题目给定的字符串的结构来决
定，由于m比较大，我们需要用矩阵来优化，根据题目给定的字符串来确定状态转移矩阵A,初始的矩阵为单
位矩阵I，，然后ans = A^(m-1)*I.在确定A的时候注意给字符串去重。
代码如下：
#include <iostream>#include <string>#include <cstring>#include <algorithm>#include <cstdio>#include <set>using namespace std;const int maxn = 55;typedef long long LL;const LL mod = 1e9+7;int n,m,cnt;string str[maxn];set<string > st;struct matrix{LL a[maxn][maxn];matrix(){memset(a,0,sizeof(a));}};matrix I,A;void init(){for(int i=0;i<maxn;i++)for(int j=0;j<maxn;j++)I.a[i][j]=(i==j);}int judge(string a,string b){for(int j=2;j<=a.length()&&j<=b.length();j++){bool tag = 0;for(int i=0;i<j;i++){if(a[a.length()-j+i]!=b[i]){tag=1;break;}}if(!tag) return 1;}return 0;}void getA(){for(int i=0;i<cnt;i++){for(int j=0;j<cnt;j++){A.a[i][j]=judge(str[i],str[j]);}}}matrix multi(matrix A,matrix B){matrix C;for(int i=0;i<cnt;i++){for(int j=0;j<cnt;j++){for(int k=0;k<cnt;k++){C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j]%mod)%mod;}}}return C;}LL quick(matrix A,int b){matrix ans=I;while(b){if(b&1) ans=multi(ans,A);b>>=1;A=multi(A,A);}LL sum=0;for(int i=0;i<cnt;i++){for(int j=0;j<cnt;j++){sum=(sum+ans.a[i][j])%mod;}}return sum;}int main(){init();int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);if(n==0||m==0){puts("0");continue;}string s;st.clear();cnt=0;for(int i=0;i<n;i++){cin>>s;if(st.find(s)==st.end()){str[cnt++]=s;st.insert(s);}}getA();init();printf("%I64d\n",quick(A,m-1));}return 0;}/****55 50121 123 213 132 3211 0 0 1 00 1 0 0 00 0 1 0 10 0 1 1 00 0 0 1 1797922656**/
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇HDU 5317 RGCDQ (素因子分解+预处理)
顶0踩0
爱情要完结的时候自会完结，到时候，你不想画上句号也不行。
