题解 P2544 【[AHOI2004]数字迷阵】

IsoTls · 2020-05-02 13:13:21 · 题解

很明显，这个题目只要确定了每一行的第一个数，该行所有的数就都确定了。 在数学上，每个正整数都可以写成若干个不重复的斐波那契数之和。为了证明这个结论，先证明引理一。

引理一： 如果已知某个斐波那契数为 F_n，下一个斐波那契数为 F_{n+1}，那么 F_n < F_{n+1} < 2*F_n

证明：

如果限定没有相邻的 1 ，这种表示法是唯一的。

既然题目中给出的表和斐波那契数有关，如果我们把表中每个整数转换成斐波那契进制，说不定会有什么发现。转换之后如下

先观察每一行，可以发现，每行第一列的最末位都是 1。将第一列的数字左移一位后得到第二列，左移两位后得到第三列，以此类推。

再观察第一列，因为最末位是 1，而斐波那契进制要求不能有连续的1，所以第一列的数字形式为 ------01，这为我们计算第一列的数提供了方便。又由于第一列的数是最小的之前从未出现过的数，所以把行号减一转换成斐波那契数进制即可。

比如要求第 10 行的第一个数，可以将 9 转换为斐波那契进制为：10001，后面再补一个 01 即为：1000101

这样就求得了第 i 行的第一个数，然后再通过左移 j-1 次，可以得到第 i 行，第 j 列的数。

代码如下：

#include <stdio.h>
#define MAX 1000000000
#define SIZE 256

int bits[SIZE];
int fib[SIZE] = {1, 1, 2};
int fib_len;
int shifted[SIZE];

struct Matrix {
    int m[2][2];
    Matrix() {
        m[0][0] = 1; m[0][1] = 1;
        m[1][0] = 1; m[1][1] = 0;
    }
};

int find_lower(int value) {
    int low = 0;
    int high = fib_len - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (fib[mid] <= value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low - 1;
}

int fill_bits(int value) {
    bits[0] = 1;
    bits[1] = 0;
    value--;
    int len = find_lower(value);
    int k = len;
    while (k > 0 && value > 0) {
        if (value >= fib[k]) {
            bits[k+1] = 1; 
            value -= fib[k];
        }
        k--;
    }
    return len + 2;
}

Matrix matrix_mul(const Matrix* a, const Matrix* b, int M) {
    Matrix c;
    c.m[0][0] = (a->m[0][0] * b->m[0][0] + a->m[0][1] * b->m[1][0]) % M;
    c.m[0][1] = (a->m[0][0] * b->m[0][1] + a->m[0][1] * b->m[1][1]) % M;
    c.m[1][0] = (a->m[1][0] * b->m[0][0] + a->m[1][1] * b->m[1][0]) % M;
    c.m[1][1] = (a->m[1][0] * b->m[0][1] + a->m[1][1] * b->m[1][1]) % M;
    return c;
}

Matrix matrix_pow(const Matrix* matrix, int n, int M) {
    if (n == 1) {
        return {};
    }
    Matrix t = matrix_pow(matrix, n/2, M);
    t = matrix_mul(&t, &t, M);
    if (n & 1) {
        return matrix_mul(&t, matrix, M);
    }
    return t;
}

void get_shifted_fib(int j, int k, int M) {
    if (j == 0) {
        shifted[0] = 1 % M;
        shifted[1] = 2 % M;
    } else {
        Matrix c;
        c = matrix_pow(&c, j, M);
        shifted[0] = (c.m[1][0] * 2 + c.m[1][1]) % M;
        shifted[1] = (c.m[0][0] * 2 + c.m[0][1]) % M;
    }
    for (int i = 2; i <= k; i++ ) {
        shifted[i] = (shifted[i-1] + shifted[i-2]) % M;
    }
}

int main() {
    int i, j, m, k;
    for (k = 2; fib[k-1] < MAX; k++) {
        fib[k] = fib[k-1] + fib[k-2];
    }
    fib_len = k - 1;

    scanf("%d%d%d", &i, &j, &m);
    k = fill_bits(i); // 计算第 i 行，第一列的数
    get_shifted_fib(j-1, k, m);  // 左移 j-1 位
    int ans = 0;
    for (i = 0; i <= k; i++) {
        if (bits[i]) { // 按位计算
            ans = (ans + shifted[i]) % m; 
        }
    }
    printf("%d\n", ans);
    return 0;
}