2017-2018 ACM-ICPC Southwestern European Regional Programming Contest - C.Macarons

原题面

描述

Pierre is famous for his macarons. He makes round macarons, stored in square boxes of size , and oval-shaped macarons, stored inrectangular boxes of size (or, rotated, in rectangular boxes of size ). For the purpose of a buffet, Pierre wishes to tile a rectangular table of size with the two kinds of macarons, meaning that the table must be completely full, with no empty space left. The width of the table is small, for the guest to be able to grab the macarons easily, and the length of the table is large, to accommodate a huge number of guests. To keep the table pretty, the orientation of macarons should always be aligned with the sides of the table.
Pierre wishes to know how many ways there are to tile the table. Can you help him?

输入

The input consists of the following integers:
the value of , an integer, on the first line;
the value of , an integer, on the second line.

输出

The output should consist of the total number of tilings, given modulo , on a single line.

数据范围

The input satisfies and .

时空限制

时间限制：
空间限制：

样例

输入	输出
2 2	7
2 4	71

链接

https://nanti.jisuanke.com/t/A1560

题解

题意

用、和的色块填满整个个单元格组成的格网。

思路

下面、和的色块分别用红色、蓝色、绿色表示。
考虑的情况，即一个两行两列的格网，左边一列称为cur，右边一列称为next。并规定一列从上至下，若一个单元格被填充（红色）则为1，否则（白色）为0。
由于最终目的是填满整个格网，故必须保证cur全填满（并保证从上至下依次填充）的情况下再填充next。
考虑在此情况下，还能填充的单元格。很显然只有红色单元格下面的一个的单元格可以被填充，可以填充或者的色块，如下图。
把每列从上至下看成一个二进制数（最上对应最低位，最下对应最高位），则得到将cur从初始状态01填满为11并转移至next的00和10两种途径，转化为十进制分别对应和。
还是的情况，再考虑全空的情况，将cur从初始状态00填满共有五种情况，如下图所示，分别转移至next的00、00、01、10和11状态，转化为十进制分别对应、、、和。
构造数组，表示从（的二进制）所代表的cur的初始状态填满为（其二进制表示为个1）并转移至next的（的二进制）所代表的状态的所有方案数。如上图可得到、、和。
因此可以遍历cur的所有可能的初始状态，即从到，枚举出由此初始状态可以转移至next的所有可能状态的方案数，从而构造出完整的矩阵。由于色块的最大宽度为，故在cur中填充色不会对next右边的空格网产生影响。如当时，构造出的矩阵为 $T=\begin{bmatrix}2&1&1&1\\1&0&1&0\\1&1&0&0\\1&0&0&0\end{bmatrix}$
设当前处于的列cur的状态为，下一列tran的状态为，再下一列next的状态为，则。当tran为第列时，假象存在next列，其状态为。
由此可得到答案为。
由于，需要用矩阵快速幂快速计算矩阵乘法。

时间复杂度

矩阵大小
矩阵乘法
快速幂
合计

代码

#include <cstdio>
int const N = 1 << 8;
long long const mod = 1000000000ll;
int n, target;
long long m, T[N][N], ans[N][N], t[N][N];
void dfs(int init, int cur, int next) {
    int fzp = -1; // 第一个为0的位
    for (int i = 0; i < n; ++i)
        if (!(cur & (1 << i))) { // 判断cur的二进制从低至高的第i位是否为0
            fzp = i;
            break;
        }
    if (fzp == -1) {
        ++T[init][next]; // 找到一种将cur从初始状态init填满并转移至next的途径
        return;
    }
    dfs(init, cur | (1 << fzp), next); // 1×1
    dfs(init, cur | (1 << fzp), next | (1 << fzp)); // 1×2
    if (fzp < n - 1 && !(cur & (1 << (fzp + 1))))
        dfs(init, cur | (1 << fzp) | (1 << (fzp + 1)), next); // 2×1
}
// 矩阵乘法，A *= B
void times(long long a[N][N], long long b[N][N]) {
    long long sum;
    for (int i = 0; i <= target; ++i)
        for (int j = 0; j <= target; ++j) {
            sum = 0ll;
            for (int k = 0; k <= target; ++k)
                sum = (sum + a[i][k] * b[k][j]) % mod;
            t[i][j] = sum;
        }
    for (int i = 0; i <= target; ++i)
        for (int j = 0; j <= target; ++j)
            a[i][j] = t[i][j];
}
// 矩阵快速幂，ans = T ^ m
void fpower(long long ans[N][N], long long T[N][N], long long m) {
    for (int i = 0; i <= target; ++i)
        for (int j = 0; j <= target; ++j)
            ans[i][j] = (long long)(i == j);
    while (m) {
        if (m & 1)
            times(ans, T);
        times(T, T);
        m >>= 1;
    }
}
int main() {
    scanf("%d%lld", &n, &m);
    target = (1 << n) - 1; // target = 2 ^ n - 1
    for (int i = 0; i <= target; ++i)
        for (int j = 0; j <= target; ++j)
            T[i][j] = 0ll;
    for (int i = 0; i <= target; ++i)
        dfs(i, i, 0);
    // for (int i = 0; i <= target; ++i) {
    //     for (int j = 0; j <= target; ++j)
    //         printf("%lld ", T[i][j]);
    //     printf("\n");
    // }
    fpower(ans, T, m);
    printf("%lld\n", ans[0][0]);
    return 0;
}