2387 - 兔农
时间限制 : 1 秒
内存限制 : 256 MB
农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小 朋友在讨论兔子繁殖的问题。 问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这 对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后 又能每个月生出一对小兔子。问第 n 个月有多少只兔子？ 聪明的你可能已经发现，第 n 个月的兔子数正好是第 n 个 Fibonacci(斐波那 契)数。栋栋不懂什么是 Fibonacci 数，但他也发现了规律：第 i+2 个月的兔子数 等于第 i 个月的兔子数加上第 i+1 个月的兔子数。前几个月的兔子数依次为： 1 1 2 3 5 8 13 21 34 … 栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋 在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每 k 对兔子围 成一圈，最后剩下的不足 k 对的围成一圈，由于兔子特别害怕孤独，从第三个月 开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。 例如，当 k=7 时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 … 给定 n，你能帮助栋栋计算第 n 个月他有多少对兔子么？由于答案可能非常 大，你只需要告诉栋栋第 n 个月的兔子对数除 p 的余数即可。
题目输入
输入一行，包含三个正整数 n, k, p。
题目输出
输出一行，包含一个整数，表示栋栋第 n 个月的兔子对数除 p 的余数。
输入/输出样例
输入格式
6 7 100
输出格式
7
C++解答
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <string> typedef long long int64; const int maxK = 1000010; struct Matrix { int ele[3][3]; static int Mod; Matrix() {memset(ele, 0, sizeof ele);} Matrix(const Matrix& b) {*this = b;} Matrix& operator=(const Matrix& b) {memcpy(ele, b.ele, sizeof ele); return *this;} int* const operator[](const int& Ind) {return ele[Ind];} const int* const operator[](const int& Ind) const {return ele[Ind];} Matrix& operator*=(const Matrix& b) { static Matrix res; for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) { int64 tmp = 0; for (int k = 0; k < 3; ++k) tmp += (int64)ele[i][k] * b[k][j]; res[i][j] = tmp % Mod; } return *this = res; } } matr[maxK], A, B, C; int Fib[maxK << 3], Ind_Fib[maxK], Ind_Cyc[maxK], len[maxK], p, K, Matrix::Mod = 0; int64 n; Matrix pow(const Matrix& a, int64 n) { Matrix res, tmp(a); res[0][0] = res[1][1] = res[2][2] = 1; for (; n; n >>= 1, tmp *= tmp) if (n & 1) res *= tmp; return res; } int pow(int a, int64 n, int Mod) { int64 res = 1, tmp = a; for (; n; n >>= 1, (tmp *= tmp) %= Mod) if (n & 1) (res *= tmp) %= Mod; return res; } int gcd(int n, int m) { for (int r; m; n = m, m = r) r = n % m; return n; } int main() { scanf("%lld%d%d", &n, &K, &p); Matrix::Mod = p; Fib[1] = Fib[2] = 1; for (int i = 3; ; ++i) { Fib[i] = (Fib[i - 1] + Fib[i - 2]) % K; if (!Ind_Fib[Fib[i]]) Ind_Fib[Fib[i]] = i; if (Fib[i] == 1 && Fib[i - 1] == 1) break; } int tmp = K, mul_Inv = 1; for (int i = 2; i * i <= tmp; ++i) if (tmp % i == 0) { mul_Inv *= i - 1; while ((tmp /= i) % i == 0) mul_Inv *= i; } if (tmp > 1) mul_Inv *= tmp - 1; A[0][1] = A[1][0] = A[1][1] = A[2][2] = 1; B[0][0] = B[1][1] = B[2][2] = 1; C[0][0] = C[1][1] = C[2][2] = 1; memset(Ind_Cyc, 0xff, sizeof Ind_Cyc); int tot = 0, ths = 1, ans = 0; int64 totlen = 0; for (; Ind_Cyc[ths] == -1; ++tot) { if (gcd(ths, K) > 1 || !Ind_Fib[pow(ths, mul_Inv - 1, K)]) { for (int i = 0; i < tot; ++i) B *= matr[i]; B *= pow(A, n - totlen); ans = ((B[1][0] - B[2][0]) % p + p) % p; printf("%d\n", ans); return 0; } Ind_Cyc[ths] = tot; int nxt = pow(ths, mul_Inv - 1, K); len[tot] = Ind_Fib[nxt]; if (n < totlen + len[tot]) { for (int i = 0; i < tot; ++i) B *= matr[i]; B *= pow(A, n - totlen); ans = ((B[1][0] - B[2][0]) % p + p) % p; printf("%d\n", ans); return 0; } totlen += len[tot]; matr[tot] = pow(A, len[tot]); ++matr[tot][2][0] %= p; ++matr[tot][2][1] %= p; ths = ((int64)ths * Fib[len[tot] - 1]) % K; } int start = Ind_Cyc[ths]; for (int i = 0; i < start; ++i) B *= matr[i], n -= len[i]; totlen = 0; for (int i = start; i < tot; ++i) C *= matr[i], totlen += len[i]; B *= pow(C, n / totlen); n %= totlen, totlen = 0; for (int i = start; i < tot; ++i) { if (n < totlen + len[i]) { B *= pow(A, n - totlen); ans = ((B[1][0] - B[2][0]) % p + p) % p; printf("%d\n", ans); return 0; } B *= matr[i]; totlen += len[i]; } return 0; }