自动搬运

查看原文

来自洛谷，原作者为

	IsoTls **

搬运于2025-08-24 21:38:52，当前版本为作者最后更新于2020-05-02 13:13:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

证明：

$F_n < F_n + F_{n-1} = F_{n+1}$，(1)

$F_{n+1} = F_n + F_{n-1} < F_n + F_n = 2*F_n$，(2)

结合（1）（2）得证。

定理：每个正整数都可以写成若干个不重复的斐波那契数之和。

可以用数学归纳法证明：

（1）当 $N=1$ 时，$1 = 1$ 显然成立。

（2）当 $N > 1$时，假设对于所有小于 $N$ 的正整数，都成立。

如果 $N$ 本身就是斐波那契数，那么显然 $N = N$ 成立。

如果 $N$ 不是斐波那契数，我们可以找到小于 $N$ 的最大斐波那契数 $K$。由归纳假设可知 $N - K$ 可以写成若干不重复的斐波那契数之和。由引理一可知，在 $K$ 和 $2*K$ 之间必然存在另外一个斐波那契数。既然 $K$ 是小于 $N$ 的最大斐波那契数，$N$ 和 $K$ 必然满足关系：$N < 2*K$ ，因此 $N-K < K$。而 $N = K + (N - K)$，所以 $N$ 也可以写成若干不重复的斐波那契数之和。

综合(1),(2)得证。

再加上零，这样我们就可以把每个整数写成斐波那契进制。具体的做法是将整数 $N$ 写成若干斐波那契数之和，把对应斐波那契数的位置填 $1$ ，其他位置填 $0$。如以下列表：

$0 = 0$

$1 = 1$

$2 = 10$

$3 = 100$

$4 = 3 + 1 = 101$

$5 = 1000$

$6 = 5 + 1 = 1001$

$7 = 5 + 2 = 1010$

$8 = 10000$

$9 = 8 + 1 = 10001$

$...$

如果限定没有相邻的 $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;
}