hdu2604（Trie图的应用）

77 阅读 0 评论 51 点赞

我是靠谱客的博主畅快黑米，最近开发中收集的这篇文章主要介绍hdu2604（Trie图的应用），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：在串中不能出现fmf和fff。

思路分析：用Trie图的思想，手动建立Trie图，然后构造矩阵，矩阵的n次幂，就是长度为n的串。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6
using namespace std;
int MOD;
struct Matrix
{
    int m[10][10];
    Matrix()
    {
        memset(m,0,sizeof(m) );
    }
}A,I;
void init()
{
    A.m[0][0] = A.m[0][1] = 1;
    A.m[1][2] = A.m[1][4] = 1;
    A.m[2][0] = 1;
    A.m[3][2] = A.m[3][4] = 1;
    A.m[4][2] = 1;
    A.m[5][2] = 1;
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            if(i == j)
                I.m[i][j] = 1;
            else I.m[i][j] = 0;
}
Matrix matrixmul(Matrix a,Matrix b,int k)
{
    Matrix c;
    int i,j,o;
    for(i = 0; i < k; i++)
        for(j = 0; j < k; j++)
            for(o = 0;o < k; o++)
                c.m[i][j] = (c.m[i][j] + a.m[i][o]*b.m[o][j])%MOD;
    return c;
}
Matrix matrixpow(Matrix a,int n,int k)
{
    Matrix b = I;
    while(n)
    {
        if(n&1)     b = matrixmul(b,a,k);
        a = matrixmul(a,a,k);
        n/=2;
    }
    return b;
}
int main()
{
    int l,m;
    init();
    while(scanf("%d%d",&l,&MOD) != EOF)
    {
        if(l == 0)
            printf("0n");
        else if(l == 1)
            printf("2n");
        else if(l == 2)
            printf("4n");
        else
        {
            Matrix ans;
            ans = matrixpow(A,l,6);
            int res = 0;
            for(int i = 0; i < 6; i++)
                res = (res + ans.m[0][i])%MOD;
            printf("%dn",res);
        }
    }
    return 0;
}