hdu 2604(矩阵快速幂)

77 阅读 0 评论 51 点赞

我是靠谱客的博主火星上丝袜，最近开发中收集的这篇文章主要介绍hdu 2604(矩阵快速幂)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：f和m两种字母，给出l表示有2^l个由f和m组成长度为l的字符串，如果这些字符串内包含fmf或fff子串的是一种特殊字符串，给出l问不是特殊字符串的数量是多少。
题解：先暴力把前几个l的答案跑了一下，发现有个规律f(n) = f(n - 1) + f(n - 3) + f(n - 4)，试着用这个公式写了矩阵快速幂交上去过了，但后来发现这个规律是有原因的，如果以m为最后一个字符的答案有f(n - 1)个，但如果以f为结尾就不一定了，两个字符结尾会有ff,mf,然而也无法判定，所以继续三个字符结尾fff,fmf,mmf,mff,其中肯定没答案的是fff和fmf，如果以mmf为结尾解就有f(n - 3)，如果以mff就无法确定，继续向前推，四个字符结尾有fmff,mmff，fmff肯定无解，那么mmff为结尾的解就有f(n - 4)，自此结束，所以情况都可以判定下来，所以f(n) = f(n - 1) + f(n - 3) + f(n - 4)。构造矩阵，然后用矩阵快速幂就可以得到答案。

#include <stdio.h>
#include <string.h>
const int N = 10;
struct Mat {
    int g[N][N];
}res, ori;
int l, m;

Mat multiply(Mat x, Mat y) {
    Mat temp;
    memset(temp.g, 0, sizeof(temp.g));
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++)
                temp.g[i][j] = (temp.g[i][j] + x.g[i][k] * y.g[k][j]) % m;
    return temp;
}

void calc(int n) {
    while (n) {
        if (n & 1)
            ori = multiply(ori, res);
        n >>= 1;
        res = multiply(res, res);
    }
}

int main() {
    while (scanf("%d%d", &l, &m) == 2) {
        if (l == 1)
            printf("%dn", 2 % m);
        else if (l == 2)
            printf("%dn", 4 % m);
        else if (l == 3)
            printf("%dn", 6 % m);
        else if (l == 4)
            printf("%dn", 9 % m);
        else {
            memset(ori.g, 0, sizeof(ori.g));
            memset(res.g, 0, sizeof(res.g));
            res.g[0][0] = res.g[0][1] = res.g[2][0] = res.g[3][0] = res.g[1][2] = res.g[2][3] = 1;
            ori.g[0][0] = 9;
            ori.g[0][1] = 6;
            ori.g[0][2] = 4;
            ori.g[0][3] = 2;
            calc(l - 4);
            printf("%dn", ori.g[0][0]);
        }
    }
    return 0;
}