NOI2011 兔农

题目:

  农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。
  问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 个月有多少只兔子?
  聪明的你可能已经发现,第 个月的兔子数正好是第 个 Fibonacci (斐波那契)数。栋栋不懂什么是 Fibonacci 数,但他也发现了规律:第 个月的兔子数等于第 个月的兔子数加上第 个月的兔子数。前几个月的兔子数依次为:
  栋栋发现越到后面兔子数增长的越快,期待养兔子一定能赚大钱,于是栋栋在第一个月初买了一对小兔子开始饲养。 每天,栋栋都要给兔子们喂食,兔子们吃食时非常特别,总是每 对兔子围成一圈,最后剩下的不足 对的围成一圈,由于兔子特别害怕孤独,从第三个月开始,如果吃食时围成某一个圈的只有一对兔子,这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子,那么每个月的兔子数仍然是可以计算的。例如,当 时,前几个月的兔子数依次为:
  给定 ,你能帮助栋栋计算第 个月他有多少兔子么?由于答案可能非常大,你只需要告诉栋栋第 个月的兔子对数除 的余数即可。

思路:

  直接线性推一下就有 分(好良心啊qwq)。
  因为当 时, 就要减一,所以把 全部列出来会发现可以用 把这些值划成一段一段的,比如 时:
  
  
  
  然后每一段之间是不会出现兔子死亡的,所以这一段的转移都可以用矩阵转移。因为每一段的开头都是两个连续的数字,所以如果设每一段的开头为 ,这一行的第 项就是 。所以可以通过解 快速的算出每段的最后一个非零数。如果设 表示满足 最小的 ,那么这一段的长度就也能得到了,而对于 有一个这样的结论:斐波那契数列在模 意义下一定存在一个长度小于 的循环节,所以 也就直接暴力预处理了。而因为开头又是模 的,所以只要出现了重复数字就出现了循环节,这样就能保证需要计算的段数是小于 的。只要用两个矩阵进行转移即可(一个没有兔子死亡,一个会死一只兔子)。

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int K = 1e6 + 5;

ll n;
int k, p;

struct Matrix {
    int a[3][3], n, m;
    int* operator[] (int x) {return a[x];}
    Matrix() {mset(a, 0);}
    Matrix operator* (Matrix b) {
        Matrix c;
        c.n = n; c.m = b.m;
        rep(i, 0, c.n) rep(j, 0, c.m) 
            rep(k, 0, m)
                (c[i][j] += (ll) a[i][k] * b[k][j] % p) %= p;
        return c;
    }
} A, B, C, mat[K * 2];
void init_Matrix() {
    A.n = A.m = 2;
    A[0][0] = 1; A[0][1] = 0; A[0][2] = 0;
    A[1][0] = 0; A[1][1] = 0; A[1][2] = 1;
    A[2][0] = 0; A[2][1] = 1; A[2][2] = 1;

    B.n = B.m = 2;
    B[0][0] = 1; B[0][1] = 0; B[0][2] = -1;
    B[1][0] = 0; B[1][1] = 0; B[1][2] = 1;
    B[2][0] = 0; B[2][1] = 1; B[2][2] = 1;


    C.n = 0; C.m = 2;
    C[0][0] = 1; C[0][1] = 1; C[0][2] = 0;
}
Matrix qkpow(Matrix a, ll k) {
    Matrix ans = a; k--;
    for(; k; k >>= 1, a = a * a)
        if(k & 1) ans = ans * a;
    return ans;
}

void exgcd(int a, int b, int &x, int &y) {
    if(!b) {x = 1; y = 0; return;}
    exgcd(b, a % b, y, x); y -= a / b * x;
}
int inv(int a, int mod) {
    int x, y;
    if(__gcd(a, mod) != 1) return -1;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

int pos[K], fib[K * 6];
int vis[K], id[K];
ll len[K];

int main() {
    File(rabbits);
    init_Matrix();
    scanf("%lld%d%d", &n, &k, &p);
    fib[1] = fib[2] = 1;
    rep(i, 3, k * 6) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % k;
        if(!pos[fib[i]]) pos[fib[i]] = i;
    }
    ll cnt = 0;
    int val = 1, tot = 0;
    while(n) {
        if(vis[val] == 1 && n >= cnt - len[val]) {
            Matrix tmp = mat[id[val] + 1];
            rep(i, id[val] + 2, tot) tmp = tmp * mat[i];
            C = C * qkpow(tmp, n / (cnt - len[val]));
            n %= cnt - len[val];
        }
        vis[val]++; len[val] = cnt; id[val] = tot;
        int nxt = inv(val, k);
        if(nxt == - 1 || !pos[nxt] || n < pos[nxt]) {
            C = C * qkpow(A, n);
            break;
        }
        else {
            mat[++tot] = qkpow(A, pos[nxt] - 1) * B;
            C = C * mat[tot];
            n -= pos[nxt]; cnt += pos[nxt];
            val = (ll) fib[pos[nxt] - 1] * val % k;
        }
    }
    printf("%d\n", (C[0][2] + p) % p);
    return 0;
}