cjb-poi2010hamsters

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
struct matrix
{
    long long p[210][210];
    int n;
    void init(int _n)
    {
        n=_n;
        memset(p,0,sizeof(p));
        rep(i,n)rep(j,n)p[i][j]=1ll*2147483647*1000000;
    }
    friend matrix operator *(const matrix& a,const matrix& b)
    {
        matrix c; c.init(a.n);
        rep(i,c.n)rep(j,c.n)rep(k,c.n)c.p[i][j]=min(c.p[i][j],a.p[i][k]+b.p[k][j]);
        return c;
    }
}f;
string s[210];
int n,m;
char ss[110000];
void getstr(string &s)
{
    scanf("%s",ss+1);
    int n=strlen(ss+1);
    s="";
    rep(i,n)s=s+ss[i];
}
int f1[110000],f2[110000],p[110000];
int get(string x,string y)
{
    int len1=x.length();
    f1[len1+1]=0; for(int i=len1;i>=1;i--)f1[i]=(1ll*f1[i+1]+1ll*p[len1-i]*x[i-1])%998244353;
    int len2=y.length();
    f2[0]=0; rep(i,len2)f2[i]=(1ll*f2[i-1]*37+y[i-1])%998244353;

    int t=0;
    for(int i=1;i<min(len1,len2);i++)
    {
        int t1=f1[len1-i+1];
        int t2=f2[i];
        if (t1==t2)t=i;
    }
    return len2-t;
}
matrix mypow(int k)
{
    if (k==0){ matrix ret; memset(ret.p,0,sizeof(ret.p)); return ret; }
    if (k==1)return f;
    matrix ret=mypow(k/2);
    ret=ret*ret;
    if (k&1)ret=ret*f;
    return ret;
}
int main()
{
    p[0]=1; rep(i,100010)p[i]=1ll*p[i-1]*37%998244353;
    cin>>n>>m;
    rep(i,n)getstr(s[i]);
    f.n=n; rep(i,n)rep(j,n)f.p[i][j]=get(s[i],s[j]);

    //rep(i,n)rep(j,n)printf("%d%c",f.p[i][j],j==n?'\n':' ');

    matrix x=mypow(m-1);

    long long ans=1ll*2147483647*1000000;
    rep(i,n)rep(j,n)ans=min(ans,(long long)s[i].length()+x.p[i][j]);
    cout<<ans<<endl;
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
struct matrix
{
    long long p[210][210];
    int n;
    void init(int _n)
    {
        n=_n;
        memset(p,0,sizeof(p));
        rep(i,n)rep(j,n)p[i][j]=1ll*2147483647*1000000;
    }
    friend matrix operator *(const matrix& a,const matrix& b)
    {
        matrix c; c.init(a.n);
        rep(i,c.n)rep(j,c.n)rep(k,c.n)c.p[i][j]=min(c.p[i][j],a.p[i][k]+b.p[k][j]);
        return c;
    }
}f;
string s[210];
int n,m;
char ss[110000];
void getstr(string &s)
{
    scanf("%s",ss+1);
    int n=strlen(ss+1);
    s="";
    rep(i,n)s=s+ss[i];
}
int f1[110000],f2[110000],p[110000];
int get(string x,string y)
{
    int len1=x.length();
    f1[len1+1]=0; for(int i=len1;i>=1;i--)f1[i]=(1ll*f1[i+1]+1ll*p[len1-i]*x[i-1])%998244353;
    int len2=y.length();
    f2[0]=0; rep(i,len2)f2[i]=(1ll*f2[i-1]*37+y[i-1])%998244353;
    int t=0;
    for(int i=1;i<min(len1,len2);i++)
    {
        int t1=f1[len1-i+1];
        int t2=f2[i];
        if (t1==t2)t=i;
    }
    return len2-t;
}
matrix mypow(int k)
{
    if (k==0){ matrix ret; memset(ret.p,0,sizeof(ret.p)); return ret; }
    if (k==1)return f;
    matrix ret=mypow(k/2);
    ret=ret*ret;
    if (k&1)ret=ret*f;
    return ret;
}
int main()
{
    p[0]=1; rep(i,100010)p[i]=1ll*p[i-1]*37%998244353;
    cin>>n>>m;
    rep(i,n)getstr(s[i]);
    f.n=n; rep(i,n)rep(j,n)f.p[i][j]=get(s[i],s[j]);
    //rep(i,n)rep(j,n)printf("%d%c",f.p[i][j],j==n?'\n':' ');
    matrix x=mypow(m-1);
    long long ans=1ll*2147483647*1000000;
    rep(i,n)rep(j,n)ans=min(ans,(long long)s[i].length()+x.p[i][j]);
    cout<<ans<<endl;
    return 0;
}