每日一题

题意：用1 X 2的矩形填充4 X n的矩形，共有多少种不同方法。

思路：原来写过一个2*n的，递推推公式就行。
如果n-1行填满的话，第n行只有一种情况，如果n-2行填满的话，有4种情况；

如果n-3行填满的话，有2种情况；

如果n-4行填满的话，有3种情况；

如果n-5行填满的话，有2种情况；

如果n-6行填满的话，有3种情况；

...

f[n] = f[n-1] + 4*f[n-2] + 2 * [ f[n-3] + f[n-5] + f[n-7] +.... ] + 3 * [ f[n-4] + f[n-6] + f[n-8] +... ] ; (1)

f[n - 2] = f[n-3] + 4*f[n-4] + 2 * [ f[n-5] + f[n-7] + f[n-9]+..] + 3 * [ f[n-6] + f[n-8] + f[n-10] +.. ] ;(2)

(1) - (2) 化简得 f[n] = f[n-1] + 5f[n-2] + f[n-3] - f[n-4]；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
int a[4], n, m;
typedef long long LL;
struct data{
    LL mat[4][4];
};
data mul(data a, data b)
{
    data res;
    memset(res.mat, 0, sizeof(res.mat));
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            for(int i2 = 0; i2 < 4; i2++)
                res.mat[i][j] = ((res.mat[i][j]+(a.mat[i][i2]*b.mat[i2][j])%m)%m+m)%m;
    return res;
}
int main()
{
    a[0] = 1, a[1] = 1, a[2] = 5, a[3] = 11;
    while(~scanf("%d %d", &n, &m) && n + m) {
        if(n < 4) {
            printf("%d\n", a[n] % m);
            continue;
        }
        n -= 3;
        data base, res;
        memset(base.mat, 0, sizeof(base.mat));
        memset(res.mat, 0, sizeof(res.mat));
        for(int i = 0; i < 4; i++)
            base.mat[i][i] = 1;
        res.mat[0][0] = 1, res.mat[0][1] = 5;
        res.mat[0][2] = 1, res.mat[0][3] = -1;
        res.mat[1][0] = 1, res.mat[2][1] = 1;
        res.mat[3][2] = 1;
        while(n) {
            if(n % 2)
                base = mul(res, base);
            res = mul(res, res);
            n >>= 1;
        }
        LL res2 = 0;
        for(int i = 0; i < 4; i++)
            res2 = (res2 + (base.mat[0][i] * a[3 - i])%m)%m;
        printf("%lld\n", res2);
    }
    return 0;
}