首页 > 分享 > 【BZOJ2085】【POI2010】—Hamsters（哈希+矩阵快速幂）

【BZOJ2085】【POI2010】—Hamsters（哈希+矩阵快速幂）

萌宠菠菠乐园
2025-01-06 21:51

传送门

Description

Tz养了一群仓鼠，他们都有英文小写的名字，现在Tz想用一个字母序列来表示他们的名字，只要他们的名字是字母序列中的一个子串就算，出现多次可以重复计算。现在Tz想好了要出现多少个名字，请你求出最短的字母序列的长度是多少。

Input

输入：第一行n（1<=n<=200）和m(1<=m<=10的9此方)，n表示有多少个仓鼠，m表示Tz希望出现名字的次数，接下来n行，每行都是仓鼠的名字（中间没有空格）。

Output

输出：一行，最短的字母序列的长度。

Sample Input

4 5

monika

tomek

szymon

bernard

Sample Output

考虑对每一对仓鼠预处理出接过来最少需要的字符

发现这个和图上走 m m m步的最短路径很类似
矩乘优化即可

复杂度 O ( n 3 l o g m ) O(n^3logm) O(n3logm)

#include<bits/stdc++.h> using namespace std; #define gc getchar inline int read(){char ch=gc();int res=0,f=1;while(!isdigit(ch))f^=ch=='-',ch=gc();while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();return f?res:-res; } #define ll long long #define pb push_back #define pii pair<int,int> #define fi first #define se second #define uint unsigned int const int N=205; int n,m; inline void chemx(ll &a,ll b){a=a>b?a:b; } inline void chemn(ll &a,ll b){a=a>b?b:a; } struct mat{ll a[N][N];mat(){memset(a,127/3,sizeof(a));}friend inline mat operator *(const mat &a,const mat &b){mat c=mat();for(int i=1;i<=n;i++)for(int k=1;k<=n;k++)for(int j=1;j<=n;j++)chemn(c.a[i][j],a.a[i][k]+b.a[k][j]);return c;} }; inline mat ksm(mat a,int b,mat res){for(;b;b>>=1,a=a*a)(b&1)&&(res=res*a,1);return res; } char a[100005]; uint f[N][100005],p[100005]; const uint bas=31; mat res,now; int len[N]; inline int calc(int a,int b){for(int l=min(len[a],len[b])-1,i=l;i;i--)if(f[a][len[a]]-f[a][len[a]-i]*p[i]==f[b][i])return i;return 0; } signed main(){n=read(),m=read();p[0]=1;for(int i=1;i<100005;i++)p[i]=p[i-1]*bas;for(int i=1;i<=n;i++){scanf("%s",a+1);len[i]=strlen(a+1);for(int j=1;j<=len[i];j++)f[i][j]=f[i][j-1]*bas+a[j];}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)res.a[i][j]=len[j]-calc(i,j),now.a[i][j]=0;if(m>1)now=ksm(res,m-2,res);ll ans=1e18;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)chemn(ans,len[i]+now.a[i][j]);cout<<ans; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465