hdu2604

标签：满足条件 那么 mff int hdu2604 fff

用f(n)表示n个人满足条件的结果，那么如果最后一个人是m的话，那么前n-1个满足条件即可，就是f(n-1)； 
如果最后一个是f那么这个还无法推出结果，那么往前再考虑一位：那么后三位可能是：mmf, fmf, mff, fff，其中fff和fmf不满足题意所以我们不考虑，但是如果是 
mmf的话那么前n-3可以找满足条件的即：f(n-3)；如果是mff的话，再往前考虑一位的话只有mmff满足条件即：f(n-4) 
所以f(n)=f(n-1)+f(n-3)+f(n-4)，递推会跪，可用矩阵快速幂 
构造一个矩阵： 

 

打表法：

#include<iostream>
using namespace std;
#define N 1000001
#define M 30

int res[N][M+1];
void init() {
    for (int i = 1; i <= M; i++)
    {
        res[1][i] = 2 % i;
        res[2][i] = 4 % i;
        res[3][i] = 6 % i;
        res[4][i] = 9 % i;
        for (int j = 5; j < N; j++)
        {
            res[j][i] = (res[j - 1][i] + res[j - 3][i] + res[j - 4][i]) % i;
        }
    }
}

int main() {
    init();
    int n, m;
    while (cin >> n >> m)
    {
        printf("%d\n", res[n][m]);
    }
    return 0;
}

 

标签：满足条件,那么,mff,int,hdu2604,fff
From： https://www.cnblogs.com/xiaohuangTX/p/18370352