记录编号	601051	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1374.[NOI 2011]兔农	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.942 s
提交时间	2025-05-27 21:23:27	内存使用	9.51 MiB

#include <cstdio>
#include <cstring>
#define min(__x, __y) [&](auto _x, auto _y) {return _x < _y ? _x : _y;} (__x, __y)
typedef long long ll;

const int MAX = 1e6 + 10;
const int SIZE = 3;

ll p;

struct Matrix {
  ll o[SIZE + 1][SIZE + 1];

  Matrix() {
    memset(o, 0, sizeof o);
  }

  ll* operator [](int val) {
    return o[val];
  }
} mat, tr1, tr2, tr;

Matrix operator * (Matrix x, Matrix y) {
  Matrix res;
  for (int k = 1; k <= SIZE; ++k) {
    for (int i = 1; i <= SIZE; ++i) {
      for (int j = 1; j <= SIZE; ++j) {
        res[i][j] = (res[i][j] + x[i][k] * y[k][j] + p) % p;
      }
    }
  }
  return res;
}

Matrix kasumi(Matrix a, ll b) {
  Matrix res;
  for (int i = 1; i <= SIZE; ++i) res[i][i] = 1;

  while (b) {
    if (b & 1) res = res * a;
    b >>= 1;
    a = a * a;
  }
  return res;
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll z = x;
  x = y;
  y = z - (a / b) * y;
  return d;
}

ll getinverse(ll a, ll mod) {
  ll x, y;
  if (exgcd(a, mod, x, y) != 1) return -1;
  return (x % mod + mod) % mod;
}

ll n, k;
ll len[MAX]; // len[i] : 以数字 i 开头的段的长度
ll f[6 * MAX]; // f[i] : 正常的斐波那契数列第 i 位
ll kcnt;
ll seq[MAX]; // seq[i] : 第 i 段段开头的数
ll vis[MAX]; // vis[i] : 数字 i 作为开头在第几个段
bool flag;

int main() {
  freopen("noi2011_rabbit.in", "r", stdin);
  freopen("noi2011_rabbit.out", "w", stdout);
  scanf("%lld %lld %lld", &n, &k, &p);

  if (n == 1 || n == 2) {
    printf("1\n");
    return 0;
  }

  memset(len, 0x7f, sizeof len); // 初始化 len 数组为无穷大
  f[1] = f[2] = 1; // 边界 f[1] = f[2] = 1

  for (ll i = 3; ; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) % k; // 计算 f[i]
   // printf("i=%lld f[i]=%lld\n", i, f[i]);
    if (f[i] % k == 1 && len[1] == 0x7f7f7f7f7f7f7f7f) len[1] = i; // 需要特殊计算 1 开头的段长度
    if (f[i] == 1 && f[i - 1] == 1) break;
    ll inv = getinverse(f[i], k);
    if (inv != -1) len[inv % k] = min(len[inv % k], i);
  }
  //for (ll i = 1; i <= k - 1; ++i) {
  //  printf("len[%lld]=%lld\n", i, len[i]);
  //}

  ll now = 1, tot = 0;
  while (1) {
    seq[++kcnt] = now; // 记录第 kcnt 个段开头的数为 now
    vis[now] = kcnt; // 记录数字 now 作为开头在第 kcnt 个段
    if (len[now] == 0x7f7f7f7f7f7f7f7f) { // 没有逆元
      for (ll i = 1; i < kcnt; ++i) tot += len[seq[i]]; // 计算之前段的总长
      flag = 1; // 记录没有逆元
      break;
    }

    now = (now * f[len[now] - 1]) % k; // 跳转到段的结尾前那个数（或者说是下一段的开头）
    //printf("%lld\n", now);
    if (vis[now]) { // 这个数字之前出现过，找到循环节
      for (ll i = 1; i < vis[now]; ++i) tot += len[seq[i]]; // 计算循环节之前段的总长
      break;
    }
  }

  // 预处理三个矩阵
  mat[1][1] = mat[1][3] = 1;
  tr1[1][1] = tr1[1][2] = tr1[2][1] = tr1[3][3] = 1;
  tr2[1][1] = tr2[1][2] = tr2[2][1] = tr2[3][3] = 1, tr2[3][1] = -1;

  if (n <= tot) { // 没有逆元的段之前或 n 在循环节之前
    len[1]--; // 因为已经算出了 f[1]，所以第一段的长度要 -1
    n--; // n 也随之 -1

    for (ll i = 1; i < vis[now]; ++i) {
      if (n >= len[seq[i]]) { // n 在第 i 段之后
        mat = mat * kasumi(tr1, len[seq[i]] - 1) * tr2; // 那么就用快速幂之前算到这一段的结尾
        n -= len[seq[i]];
      } else { // 否则直接乘
        mat = mat * kasumi(tr1, n);
        printf("%lld\n", mat[1][1]);
        return 0;
      }
    }
  } else { // 有循环节
    len[1]--;
    n -= tot; // 直接计算出到循环节之前的数

    for (ll i = 1; i < vis[now]; ++i) mat = mat * kasumi(tr1, len[seq[i]] - 1) * tr2;

    if (flag) { // 没有逆元
      mat = mat * kasumi(tr1, n);
      printf("%lld\n", mat[1][1]);
    } else {
      ll loopLen = 0; // loopLen : 循环节的长度
      for (int i = 1; i <= SIZE; ++i) tr[i][i] = 1;
      for (ll i = vis[now]; i <= kcnt; ++i) { // 计算出循环节的转移矩阵
        tr = tr * kasumi(tr1, len[seq[i]] - 1) * tr2;
        loopLen += len[seq[i]];
      }
      ll tmp = n / loopLen; // 算一下 n 中有多少个完整的循环节
      mat = mat * kasumi(tr, tmp);
      n = n - loopLen * tmp; //剩下的暴力算

      for (ll i = vis[now]; i <= kcnt; ++i) {
        if (n >= len[seq[i]]) { // 假设 n 还够完整的一段
          mat = mat * kasumi(tr1, len[seq[i]] - 1) * tr2;
          n -= len[seq[i]];
        } else {
          mat = mat * kasumi(tr1, n);
          printf("%lld\n", mat[1][1]);
          return 0;
        }
      }
    }
  }
  return 0;
}