uva 10518 - How Many Calls?（矩阵快速幂）

╰半夏微凉° 2022-05-12 23:16 235阅读 0赞

题目链接：uva 10518 - How Many Calls?

公式f(n) = 2 * F(n) - 1, F(n)用矩阵快速幂求。

  1. #include <stdio.h>
  2. #include <string.h>
  3. long long n;
  4. int b;
  6. struct state {
  7.     int s[2][2];
  8.     state(int a = 0, int b = 0, int c = 0, int d = 0) {
  9.         s[0][0] = a, s[0][1] = b, s[1][0] = c, s[1][1] = d;
  10.     }
  11. }tmp(1, 0, 0, 1), c(1, 1, 1, 0);
  13. state count(const state& p, const state& q) {
  14.     state f;
  15.     for (int i = 0; i < 2; i++)
  16.         for (int j = 0; j < 2; j++)
  17.             f.s[i][j] = (p.s[i][0] * q.s[0][j] + p.s[i][1] * q.s[1][j]) % b;
  18.     return f;
  19. }
  21. state solve(long long k) {
  22.     if (k == 0) return tmp;
  23.     else if (k == 1) return c;
  25.     state a = solve(k / 2);
  27.     a = count(a, a);
  28.     if (k % 2) a = count(a, c);
  29.     return a;
  30. }
  32. int main () {
  33.     int cas = 1;
  34.     while (scanf("%lld%d", &n, &b), n || b) {
  35.         state ans = solve(n);
  36.         printf("Case %d: %lld %d %d\n", cas++, n, b,(2 * ans.s[0][0] - 1 + b) % b);
  37.     }
  38.     return 0;
  39. }

发表评论

表情：
评论列表 （有 0 条评论，235人围观）

还没有评论，来说两句吧...

相关阅读

    相关 UVA 11551(矩阵快速幂)

    题目来源:[点击打开链接][Link 1] 题目题意:题目给我们n个数和r次操作。接在输入n行，表示每次将第i个数变成它后面几个位置的和。重复r次。 题目分析:我们按照题目

    缺乏、安全感缺乏、安全感/ 0 赞/ 308 阅读