矩阵快速幂（快速幂）模板题目Decoding Genome

今天药忘吃喽~ 2022-10-14 13:51 169阅读 0赞

这类题目的难点在于，数据量大，需要用到高精度，也就是快速幂

矩阵的乘法与快速幂模板一：

const int mod = 1e9+7;
    struct Matrix
    { 
    	LL num[N][N];
    };
    Matrix mul(Matrix p,Matrix q) { 
         Matrix ret;
         for(int i=0; i<m; i++) for(int j=0; j<m; j++) { 
            ret.num[i][j] = 0;
            for(int k=0; k<m; k++) { 
               ret.num[i][j] = (ret.num[i][j] + p.num[i][k] * q.num[k][j]) % mod;
            }
         }
         return ret;
    }

矩阵乘法与快速幂模板二：

ll c[N][N];
    void mul(ll a[][N], ll b[][N])
    { 
    	memset(c, 0, sizeof(c));
    	for(int i=0;i<m;i++) 
    		for(int j=0;j<m;j++)
    			for(int k=0;k<m;k++)
    				c[i][j] = (c[i][j]+c[i][k]+c[i][k])%mod;
    	memcpy(a,c,sizeof(c));
    }

例题：  
[  
https://codeforces.com/group/vFwRVj9WjO/contest/328371/problem/H][https_codeforces.com_group_vFwRVj9WjO_contest_328371_problem_H]

#include <bits/stdc++.h>
    #define M 1000000007
    using namespace std;
    typedef long long LL;
    
    struct Matrix
    { 
        LL num[64][64];
    };
    
    LL n;
    int m,K;
    
    LL G[64][64];
    
    
    Matrix mul(Matrix p,Matrix q) { 
         Matrix ret;
         for(int i=0; i<m; i++) for(int j=0; j<m; j++) { 
            ret.num[i][j] = 0;
            for(int k=0; k<m; k++) { 
               ret.num[i][j] += p.num[i][k] * q.num[k][j];
               ret.num[i][j] %= M;
            }
         }
         return ret;
    }
    
    Matrix f()
    { 
        Matrix ret, p;
        memset(ret.num, 0, sizeof(ret.num));
        for(int i=0; i<m; i++) ret.num[i][i] = 1; // 单位矩阵
        for(int i=0; i<m; i++) for(int j=0; j<m; j++) p.num[i][j] = G[i][j]; // 不可以相连的矩阵
     
        n--; // 注意这里减一，答案才正确
        while(n)
        { 
            if(n&1)
              ret = mul(ret,p);
            p = mul(p,p);
            n >>= 1;
        }
        return ret;  
    }
     
    int main()
    { 
        while(scanf("%I64d%d%d",&n,&m,&K) == 3)
        { 
            int i,j;
            for(i=0; i<m; i++) for(j=0; j<m; j++) G[i][j] = 1;
            // 最开始，所有的i和j都是可以连在一起的
            while(K--)
            { 
                char c1,c2;
                int x,y;
                scanf("%c %c",&c1,&c2);
                x = c1>='a'&&c1<='z'?c1-'a':c1-'A'+26;
                y = c2>='a'&&c2<='z'?c2-'a':c2-'A'+26;
                G[x][y] = 0; // 这两个不可以连在一起
            }
            Matrix ansM = f();
            LL ans = 0;
            for(i=0; i<m; i++)
            { 
                for(j=0; j<m; j++)
                { 
                    ans += ansM.num[i][j];
                    ans %= M;
                }
            }
            printf("%I64d\n",ans);
        }
        return 0;
    }

第二个模板

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int i,j,k;
    using namespace std;
    #define N 100
    #define MOD 1000000007
    long long n;
    int m;
    int k;
    int indice(char x)
    { 
        if(x>='a' && x<='z') return x-'a';
        else return x-'A'+26;
    }//预处理字符转数字
     
    long long c[N][N];
    void cheng(long long a[][N],long long b[][N])
    { 
        memset(c,0,sizeof(c));
        for(int i=0; i<m; i++)
            for(int j=0; j<m; j++)
                for(int k=0; k<m; k++)
                    c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
        memcpy(a,c,sizeof(c)); // 这一步看似没太大必要
    }
     
    long long res[N][N];
    long long odd[N][N];
     
    void pow(long long p)
    { 
        memset(odd,0,sizeof(odd));
        for(int i=0; i<m; i++)
            odd[i][i]=1;
        if(p==0) // 如果是零次方，直接返回单位矩阵
        { 
            memcpy(res,odd,sizeof(odd));
            return;
        }
        while(p>1) // 开始计算
        { 
            if(p&1) 
                cheng(odd,res);
            cheng(res,res);
            p/=2;
        }
        cheng(res,odd);
    }
     
    string s;
    int main()
    { 
        cin>>n>>m>>k;
        for(int i=0; i<m; i++)
            for(int j=0; j<m; j++)
                res[i][j]=1;
        for(int i=0; i<k; i++)
        { 
            cin>>s;
            res[indice(s[0])][indice(s[1])]=0;
        }
        n--;
        pow(n);
        long long cont=0;
        for(int i=0; i<m; i++)
            for(int j=0; j<m; j++)
                cont=(cont+res[i][j])%MOD;
        cout<<cont<<endl;
        return 0;
    }

[https_codeforces.com_group_vFwRVj9WjO_contest_328371_problem_H]: https://codeforces.com/group/vFwRVj9WjO/contest/328371/problem/H