【矩阵---求A的1到N次幂之和】

引例： Matrix Power Series：

题目大意，给定矩阵A，求A^+A^+A^+...A^N。

题解：已知X=a，可以通过以下矩阵求出ans=a^+a^+...a^N ans=矩阵^n后第一行之和-=矩阵^(n+)后右上格的和-。

同理：矩阵也可以，只需要把1改为单位矩阵元即可。

左图a是常数，1就是1； 右图A是矩阵，1是单位元矩阵（主对角线是1）。

          

代码1：矩阵^N，第一行之和-1。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int N,K,Mod;

struct mat

{

    int mp[maxn][maxn],len;

    mat(int x){ len=x; memset(mp,,sizeof(mp)); }

    mat friend operator *(mat a,mat b)

    {

        mat res(a.len);

        for(int k=;k<=res.len;k++)

         for(int i=;i<=res.len;i++)

          for(int j=;j<=res.len;j++)

            res.mp[i][j]=(res.mp[i][j]+a.mp[i][k]*b.mp[k][j])%Mod;

        return res;

    }

    mat friend operator ^(mat a,int x)

    {

        mat res(a.len);

        for(int i=;i<=res.len;i++) res.mp[i][i]=;

        while(x){

            if(x&)res=res*a;  a=a*a;  x>>=;

        }   return res;

    }

};

int main()

{

    scanf("%d%d%d",&N,&K,&Mod);

    mat array(N+N);

    for(int i=;i<=N;i++)

      for(int j=;j<=N;j++){

         scanf("%d",&array.mp[i][j]);

    }

    for(int i=;i<=N;i++) array.mp[i][i+N]=array.mp[i+N][i+N]=;

    array=array^(K);

    for(int i=;i<=N;i++) array.mp[i][i+N]-=;

    for(int i=;i<=N;i++){

        for(int j=;j<N;j++)

           printf("%d ",(array.mp[i][j]+array.mp[i][j+N]+Mod)%Mod);

        printf("%d\n",(array.mp[i][N]+array.mp[i][N+N]+Mod)%Mod);

    }

    return ;

}

代码2：矩阵^N+1，右上格之和-1。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int N,K,Mod;

struct mat

{

    int mp[maxn][maxn],len;

    mat(int x){ len=x; memset(mp,,sizeof(mp)); }

    mat friend operator *(mat a,mat b)

    {

        mat res(a.len);

        for(int k=;k<=res.len;k++)

         for(int i=;i<=res.len;i++)

          for(int j=;j<=res.len;j++)

            res.mp[i][j]=(res.mp[i][j]+a.mp[i][k]*b.mp[k][j])%Mod;

        return res;

    }

    mat friend operator ^(mat a,int x)

    {

        mat res(a.len);

        for(int i=;i<=res.len;i++) res.mp[i][i]=;

        while(x){

            if(x&)res=res*a;  a=a*a;  x>>=;

        }   return res;

    }

};

int main()

{

    scanf("%d%d%d",&N,&K,&Mod);

    mat array(N+N);

    for(int i=;i<=N;i++)

      for(int j=;j<=N;j++){

         scanf("%d",&array.mp[i][j]);

    }

    for(int i=;i<=N;i++) array.mp[i][i+N]=array.mp[i+N][i+N]=;

    array=array^(K+);

    for(int i=;i<=N;i++) array.mp[i][i+N]-=;

    for(int i=;i<=N;i++){

        for(int j=;j<N;j++)

           printf("%d ",(array.mp[i][j+N]+Mod)%Mod);

        printf("%d\n",(array.mp[i][N+N]+Mod)%Mod);

    }

    return ;

}

代码3：利用二分。

--------------------分界线---------------------------

例题：HDU2243：考研路茫茫——单词情结

题意：问长度位1到L的所有单词中，有多少个不含给出的几个单词。

思路：利用矩阵得到可以26的1到N次幂。然后利用AC自动机得到基本矩阵X，再利用矩阵得到得到X^+X^+X^...X^N。

比如得到26的0到N次幂和，就有矩阵a[][]=,a[][]=,a[][]=,a[][]=;

矩阵^N后，第一行的和就是答案。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define ull unsigned long long

const int maxn=;

int ch[maxn][],cnt;

int q[maxn],head,tail,Next[maxn],tag[maxn];

char s[];

struct mat

{

    ull mp[maxn][maxn];

    mat(){memset(mp,,sizeof(mp));}

    mat init(){ memset(mp,,sizeof(mp));}

    mat friend operator *(mat a,mat b)

    {

        mat res;

        for(int k=;k<=max(cnt,);k++)

          for(int i=;i<=max(cnt,);i++)

            for(int j=;j<=max(cnt,);j++)

             res.mp[i][j]+=a.mp[i][k]*b.mp[k][j];

        return res;

    }

    mat friend operator ^(mat a,int x)

    {

        mat res;

        for(int i=;i<=cnt;i++)

            res.mp[i][i]=;

        while(x){

            if(x&) res=res*a;

            a=a*a; x>>=;

        }   return res;

    }

};

mat array;

struct ACautom

{

    void update()

    {

        cnt=head=tail=;

        memset(Next,,sizeof(Next));

        memset(tag,,sizeof(tag));

        memset(ch,,sizeof(ch));

        array.init();

    }

    void insert()

    {

        int Now=;

        for(int i=;s[i];i++){

            int x=s[i]-'a';

            if(!ch[Now][x]) ch[Now][x]=++cnt;

            Now=ch[Now][x];

        } tag[Now]=;

    }

    void build()

    {

        for(int i=;i<;i++){

            if(ch[][i]) q[++head]=ch[][i];

            if(!tag[ch[][i]]) array.mp[][ch[][i]]++;

        }

        while(tail<head){

            int u=q[++tail];

            for(int i=;i<;i++){

                if(ch[u][i]){

                    q[++head]=ch[u][i];

                    Next[ch[u][i]]=ch[Next[u]][i];

                    if(tag[Next[ch[u][i]]]) tag[ch[u][i]]=;

                }

                else ch[u][i]=ch[Next[u]][i];

                if(!tag[ch[u][i]]) array.mp[u][ch[u][i]]++;

            }

        }

        cnt++;

        for(int i=;i<=cnt;i++) array.mp[i][cnt]=;

    }

    void qpow(int K)

    {

        ull ans,res=;

        mat base;

        base.mp[][]=; base.mp[][]=;

        base.mp[][]=;  base.mp[][]=;

        base=base^K;

        ans=base.mp[][]+base.mp[][];

        array=array^K;

        for(int i=;i<=cnt;i++) res=res+array.mp[][i];

        cout<<ans-res<<endl;

    }

}Trie;

int main()

{

    int N,K;

    while(~scanf("%d%d",&N,&K)){

        Trie.update();

        for(int i=;i<=N;i++) {

            scanf("%s",s);

            Trie.insert();

        }

        Trie.build();

        Trie.qpow(K);

    }

    return ;

}