「fjWC2015」Galaxy

2015年2月3日4,6970

「题目描述」

小X进入了平行宇宙,想在某个平行宇宙开始一段生活。平行宇宙之间用长度为N的仅含有A、B、C、D四个字母的序列标识。每一个由A,B,C，D组成的长度为N的序列标识着不同的平行宇宙。

有趣的是，不同的宇宙对应着小X的不同人生，在某些宇宙中，小X的人生过得并不愉快。

小X得到了M个特征碎片，特征碎片都为长度小于10的由A,B,C,D构成的序列。如果某个平行宇宙的标识序列包含某个特征碎片（即特征碎片为宇宙序列的子串），那么小X在这个平行宇宙过得不愉快。

小X能自由的进入任何一个平行宇宙，并且小X不想进入会让他过得不愉快的平行宇宙，请问小X有多少种选择?

「输入」

第一行为M(0 <= m <= 10), N (1 <= n <=2000000000), M为标识序列的个数，N为宇宙标识序列的长度

之后M行，每行一个特征标识序列。

每行的长度不超过10。

「输出」

一个整数，表示码农的选择数 mod 100000

「样例输入」

4 3

「样例输出」

「样例解释」

如序列ABC 包含AB,为不愉快的序列

序列BBB不包含任何特征序列，为愉快的序列。

题解

用AC自动机得出转移矩阵后矩乘

T T

模板错->滚粗

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rad 100000000
#define inf 1000000000
#define ll long long 
#define eps 1e-10
#define pi acos(-1)
#define mod 100000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int tot,m,n;
int q[505];
char ch[15];
struct M{
    ll v[105][105];
    M(){
        memset(v,0,sizeof(v));    
    }      
    friend M operator*(M a,M b){
        M c;
        for(int i=1;i<=tot;i++)
            for(int j=1;j<=tot;j++)
                for(int k=1;k<=tot;k++)
                    c.v[i][j]=c.v[i][j]+(a.v[i][k]*b.v[k][j])%mod;       
        return c;
    }
    friend M operator^(M a,int b){
        M ans;
        for(int i=1;i<=tot;i++)ans.v[i][i]=1;
        for(int i=b;i;i>>=1,a=a*a)
            if(i&1)ans=ans*a;
        return ans;
    }
    friend void print(M a){
        for(int i=0;i<=tot;i++)
        {
            for(int j=0;j<=tot;j++)
                printf("%I64d ",a.v[i][j]);    
            puts("");   
        }
    }
}b;
struct trie{
    int cnt;
    int fail[505],to[505][5];
    bool danger[505];
    trie(){
        cnt=1;fail[1]=0;
        for(int i=1;i<=4;i++)to[0][i]=1;      
    }
    void insert(){
        scanf("%s",ch+1);
        int l=strlen(ch+1),now=1;
        for(int i=1;i<=l;i++)
        {
            int t=ch[i]-'A'+1;
            if(!to[now][t])to[now][t]=++cnt;
            now=to[now][t];
        }
        danger[now]=1;
    }
    void build_fail(){
        int head=0,tail=1;
        q[0]=1;
        while(head!=tail)
        {
            int now=q[head];head++;
            for(int i=1;i<=4;i++)
                if(int t=to[now][i])
                {
                	 int k=fail[now];
                	 while(!to[k][i])k=fail[k];
                	 fail[t]=to[k][i];
                	 danger[t]|=danger[to[k][i]];
                	 q[tail++]=t;
                }
        }
    }
}T;
void solve()
{
     tot=T.cnt;
     for(int i=1;i<=tot;i++)
     {
         if(T.danger[i])continue;
         for(int j=1;j<=4;j++)
         {
         	 int k=i;
         	 while(!T.to[k][j])k=T.fail[k];
         	 if(!T.danger[T.to[k][j]])b.v[T.to[k][j]][i]++;
         }
     }
     M ans;
     int res=0;
     ans.v[1][1]=1;
     ans=(b^n)*ans;
     for(int i=1;i<=tot;i++)
         res=(res+ans.v[i][1])%mod;
     printf("%d\n",res);
}
int main()
{
    //freopen("galaxy.in","r",stdin);
    //freopen("galaxy.out","w",stdout);
    m=read();n=read();
    for(int i=1;i<=m;i++)
        T.insert();
    T.build_fail();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include<set>

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define rad 100000000

#define inf 1000000000

#define ll long long

#define eps 1e-10

#define pi acos(-1)

#define mod 100000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int tot,m,n;

int q[505];

char ch[15];

struct M{

ll v[105][105];

M(){

memset(v,0,sizeof(v));

}

friend M operator*(M a,M b){

M c;

for(int i=1;i<=tot;i++)

for(int j=1;j<=tot;j++)

for(int k=1;k<=tot;k++)

c.v[i][j]=c.v[i][j]+(a.v[i][k]*b.v[k][j])%mod;

return c;

}

friend M operator^(M a,int b){

M ans;

for(int i=1;i<=tot;i++)ans.v[i][i]=1;

for(int i=b;i;i>>=1,a=a*a)

if(i&1)ans=ans*a;

return ans;

}

friend void print(M a){

for(int i=0;i<=tot;i++)

{

for(int j=0;j<=tot;j++)

printf("%I64d ",a.v[i][j]);

puts("");

}

}b;

struct trie{

int cnt;

int fail[505],to[505][5];

bool danger[505];

trie(){

cnt=1;fail[1]=0;

for(int i=1;i<=4;i++)to[0][i]=1;

}

void insert(){

scanf("%s",ch+1);

int l=strlen(ch+1),now=1;

for(int i=1;i<=l;i++)

{

int t=ch[i]-'A'+1;

if(!to[now][t])to[now][t]=++cnt;

now=to[now][t];

}

danger[now]=1;

}

void build_fail(){

int head=0,tail=1;

q[0]=1;

while(head!=tail)

{

int now=q[head];head++;

for(int i=1;i<=4;i++)

if(int t=to[now][i])

{

int k=fail[now];

while(!to[k][i])k=fail[k];

fail[t]=to[k][i];

danger[t]|=danger[to[k][i]];

q[tail++]=t;

}

}T;

void solve()

{

tot=T.cnt;

for(int i=1;i<=tot;i++)

{

if(T.danger[i])continue;

for(int j=1;j<=4;j++)

{

int k=i;

while(!T.to[k][j])k=T.fail[k];

if(!T.danger[T.to[k][j]])b.v[T.to[k][j]][i]++;

}

M ans;

int res=0;

ans.v[1][1]=1;

ans=(b^n)*ans;

for(int i=1;i<=tot;i++)

res=(res+ans.v[i][1])%mod;

printf("%d\n",res);

}

int main()

{

//freopen("galaxy.in","r",stdin);

//freopen("galaxy.out","w",stdout);

m=read();n=read();

for(int i=1;i<=m;i++)

T.insert();

T.build_fail();

solve();

return 0;

}

« 「BZOJ2754」[SCOI2012] 喵星球上的点名「fjWC2015」世界树 »

hzwer.com _ Home | http://hzwer.com

「fjWC2015」Galaxy

分类目录

热门文章

Myfriends

近期评论