');}

清北学堂p69

Author Avatar
Actinoi 10月 05, 2020

希望

直接用栈枚举即可。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. std::string back[1001], forward[1001];
  5. int back_head = 0, back_tail = 0, forward_head = 0, forward_tail = 0;
  6. int main() {
  7.     //freopen("kami.in", "r", stdin);
  8.     //freopen("kami.out", "w", stdout);
  9.     std::string s, now = "http://www.acm.org/";
  10.     while (std::cin >> s) {
  11.         if (s == "BACK") {
  12.             if (back_tail == back_head) {
  13.                 printf("Ignored\n");
  14.                 continue;
  15.             } else {
  16.                 forward_tail++;
  17.                 forward[forward_tail] = now;
  18.                 now = back[back_tail];
  19.                 back_tail--;
  20.             }
  21.         } else if (s == "FORWARD") {
  22.             if (forward_tail == forward_head) {
  23.                 printf("Ignored\n");
  24.                 continue;
  25.             } else {
  26.                 back_tail++;
  27.                 back[back_tail] = now;
  28.                 now = forward[forward_tail];
  29.                 forward_tail--;
  30.             }
  31.         } else if (s == "VISIT") {
  32.             back_tail++;
  33.             back[back_tail] = now;
  34.             std::cin >> now;
  35.             forward_tail = forward_head;
  36.         } else if (s == "QUIT") {
  37.             return 0;
  38.         }
  39.         std::cout << now << std::endl;
  40.     }
  41.     //fclose(stdin);
  42.     //fclose(stdout);
  43.     return 0;
  44. }

残

矩阵快速幂+皮萨诺周期

·矩阵快速幂

矩阵运算之矩阵乘法

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

设 A 为 P \times M 的矩阵， B 为 M \times Q 的矩阵，设矩阵 C 为矩阵 A 与 B 的乘积，

其中矩阵 C 中的第 i 行第 j 列元素可以表示为：

C_{i,j} = \sum_{k=1}^MA_{i,k}B_{k,j}

如果没看懂上面的式子，没关系。通俗的讲，在矩阵乘法中，结果 C 矩阵的第 i 行第 j 列的数，就是由矩阵 A 第 i 行 M 个数与矩阵 B 第 j 列 M 个数分别相乘再相加得到的。

矩阵乘法满足结合律，不满足一般的交换律。

利用结合律，矩阵乘法可以利用快速幂的思想来优化。

矩阵快速幂

在斐波那契数列当中， F_1 = F_2 = 1 ， F_i = F_{i - 1} + F_{i - 2}(i \geq 3) 。

如果有一道题目让你求斐波那契数列第 n 项的值，最简单的方法莫过于直接递推了。但是如果 n 的范围达到了 10^{18} 级别，递推就不行了，稳 TLE。考虑矩阵加速递推。

设 Fib(n) 表示一个 1 \times 2 的矩阵 \left[ \begin{array}{ccc}F_n & F_{n-1} \end{array}\right] 。我们希望根据 Fib(n-1)=\left[ \begin{array}{ccc}F_{n-1} & F_{n-2} \end{array}\right] 推出 Fib(n) 。

试推导一个矩阵 \text{base} ，使 Fib(n-1) \times \text{base} = Fib(n) ，即 \left[\begin{array}{ccc}F_{n-1} & F_{n-2}\end{array}\right] \times \text{base} = \left[ \begin{array}{ccc}F_n & F_{n-1} \end{array}\right] 。

怎么推呢？因为 F_n=F_{n-1}+F_{n-2} ，所以 \text{base} 矩阵第一列应该是 \left[\begin{array}{ccc} 1 \\ 1 \end{array}\right] ，这样在进行矩阵乘法运算的时候才能令 F_{n-1} 与 F_{n-2} 相加，从而得出 F_n 。同理，为了得出 F_{n-1} ，矩阵 \text{base} 的第二列应该为 \left[\begin{array}{ccc} 1 \\ 0 \end{array}\right] 。

综上所述： \text{base} = \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right] 原式化为 \left[\begin{array}{ccc}F_{n-1} & F_{n-2}\end{array}\right] \times \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right] = \left[ \begin{array}{ccc}F_n & F_{n-1} \end{array}\right]

转化为代码，应该怎么求呢？

定义初始矩阵 \text{ans} = \left[\begin{array}{ccc}F_2 & F_1\end{array}\right] = \left[\begin{array}{ccc}1 & 1\end{array}\right], \text{base} = \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right] 。那么， F_n 就等于 \text{ans} \times \text{base}^{n-2} 这个矩阵的第一行第一列元素，也就是 \left[\begin{array}{ccc}1 & 1\end{array}\right] \times \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]^{n-2} 的第一行第一列元素。

注意，矩阵乘法不满足交换律，所以一定不能写成 \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]^{n-2} \times \left[\begin{array}{ccc}1 & 1\end{array}\right] 的第一行第一列元素。另外，对于 n \leq 2 的情况，直接输出 1 即可，不需要执行矩阵快速幂。

上述内容摘自OI-wiki。

因此便可以得到矩阵快速幂的模板。

  1. #include <cstdio>
  2. #include <cstring>
  3. #define MOD 1000000007
  4. long long n, a[3], mul[3][3], res[3][3], tmp[3][3], tp[3]; 
  5. void mul_1() {
  6.     memset(tmp, 0, sizeof(tmp)); 
  7.     for(int i = 1; i <= 2; i++)
  8.         for(int j = 1; j <= 2; j++)
  9.             for(int k = 1; k <= 2; k++)
  10.                 tmp[i][j] = (tmp[i][j] + res[i][k] * mul[k][j]) % MOD; 
  11.     for(int i = 1; i <= 2; i++)
  12.         for(int j = 1; j <= 2; j++)
  13.             res[i][j] = tmp[i][j]; 
  14. }
  15. void mul_2() {
  16.     memset(tmp, 0, sizeof(tmp)); 
  17.     for(int i = 1; i <= 2; i++)
  18.         for(int j = 1; j <= 2; j++)
  19.             for(int k = 1; k <= 2; k++)
  20.                 tmp[i][j] = (tmp[i][j] + mul[i][k] * mul[k][j]) % MOD; 
  21.     for(int i = 1; i <= 2; i++)
  22.         for(int j = 1; j <= 2; j++)
  23.             mul[i][j] = tmp[i][j]; 
  24. }
  25. void solve() {
  26.     for(int i = 1; i <= 2; i++)
  27.         for(int j = 1; j <= 2; j++)
  28.             tp[i] = (tp[i] + res[i][j] * a[j]) % MOD; 
  29.     printf("%lld\n", tp[1]); 
  30. }
  31. int main() {
  32.     scanf("%lld", &n); 
  33.     if(n <= 2) {
  34.         printf("1\n"); 
  35.     } else {
  36.         a[1] = a[2] = 1; 
  37.         for(int i = 1; i <= 2; i++)
  38.             res[i][i] = 1; 
  39.         for(int i = 1; i <= 2; i++)
  40.             for(int j = 1; j <= 2; j++)
  41.                 mul[i][j] = 1; 
  42.         mul[2][2] = 0; 
  43.         n -= 2; 
  44.         while (n) {
  45.             if (n & 1) mul_1(); 
  46.             n >>= 1; 
  47.             mul_2(); 
  48.         }
  49.         solve(); 
  50.     }
  51.     return 0; 
  52. }

·皮亚诺周期

虽然我们知道了矩阵快速幂，但是， n=10^{100} ，直接求 f(f(n)) 的话无疑时间空间都得爆。

而斐波那契数列有一个很神奇的性质，皮亚诺周期。

自然数 n 的皮萨诺周期（通常记为 π(n) ）是指斐波那契数列模 n 后的周期

详见 维基百科-皮亚诺周期。

知道了这一个之后，我们就能够求 f(f(n)) 辣。

首先求 f(f(n))\ \text{mod}\ {10^9+7} 的周期，打表程序如下：

  1. #include <cstdio>
  2. #define MOD 1000000007
  3. int main() {
  4.     long long a1 = 1, a2 = 1, cnt = 2, now;
  5.     while (1) {
  6.         cnt++;
  7.         now = (a1 + a2 + MOD) % MOD;
  8.         if (now == 1 && (now + a1 + MOD) % MOD == 1) {
  9.             printf("%lld\n", cnt - 1);
  10.             return 0;
  11.         }
  12.         a2 = a1;
  13.         a1 = now;
  14.     }
  15.     return 0;
  16. }

跑了好长时间，最后输出了 2000000016 这个数字，因此 f(f(n))\ \text{mod}\ {10^9+7} 的周期就是 2000000016 。

因此， f(n) 每次可以对 2000000016 取模，反正跑出来的答案是一样的。

而 f(n) 里面的 n 最大值可达 10^{100} ，这个程序仍然没法跑，我们便求 f(n)\ \text{mod}\ 2000000016 的周期，达标程序如下：

  1. #include <cstdio>
  2. #define MOD 2000000016
  3. int main() {
  4.     long long a1 = 1, a2 = 1, cnt = 2, now;
  5.     while (1) {
  6.         cnt++;
  7.         now = (a1 + a2 + MOD) % MOD;
  8.         if (now == 1 && (now + a1 + MOD) % MOD == 1) {
  9.             printf("%lld\n", cnt - 1);
  10.             return 0;
  11.         }
  12.         a2 = a1;
  13.         a1 = now;
  14.     }
  15.     return 0;
  16. }

最后得到 f(n) 的周期为 329616 ，同理， n 每次对 329616 取模就行了。

最终程序：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. long long MOD;
  5. long long a[3], mul[3][3], res[3][3], tmp[3][3], tp[3]; 
  6. void mul_1() {
  7.     memset(tmp, 0, sizeof(tmp)); 
  8.     for(int i = 1; i <= 2; i++)
  9.         for(int j = 1; j <= 2; j++)
  10.             for(int k = 1; k <= 2; k++)
  11.                 tmp[i][j] = (tmp[i][j] + res[i][k] * mul[k][j]) % MOD; 
  12.     for(int i = 1; i <= 2; i++)
  13.         for(int j = 1; j <= 2; j++)
  14.             res[i][j] = tmp[i][j]; 
  15. }
  16. void mul_2() {
  17.     memset(tmp, 0, sizeof(tmp)); 
  18.     for(int i = 1; i <= 2; i++)
  19.         for(int j = 1; j <= 2; j++)
  20.             for(int k = 1; k <= 2; k++)
  21.                 tmp[i][j] = (tmp[i][j] + mul[i][k] * mul[k][j]) % MOD; 
  22.     for(int i = 1; i <= 2; i++)
  23.         for(int j = 1; j <= 2; j++)
  24.             mul[i][j] = tmp[i][j]; 
  25. }
  26. long long solve() {
  27.     for(int i = 1; i <= 2; i++)
  28.         for(int j = 1; j <= 2; j++)
  29.             tp[i] = (tp[i] + res[i][j] * a[j]) % MOD; 
  30.     return tp[1]; 
  31. }
  32. long long pow(long long n, long long mo) {
  33.     memset(a, 0, sizeof(a));
  34.     memset(mul, 0, sizeof(mul));
  35.     memset(res, 0, sizeof(res));
  36.     memset(tmp, 0, sizeof(tmp));
  37.     memset(tp, 0, sizeof(tp));
  38.     if(n <= 2) {
  39.         return 1; 
  40.     } else {
  41.         MOD = mo;
  42.         a[1] = a[2] = 1; 
  43.         for(int i = 1; i <= 2; i++)
  44.             res[i][i] = 1; 
  45.         for(int i = 1; i <= 2; i++)
  46.             for(int j = 1; j <= 2; j++)
  47.                 mul[i][j] = 1; 
  48.         mul[2][2] = 0; 
  49.         n -= 2; 
  50.         while (n) {
  51.             if (n & 1) mul_1(); 
  52.             n >>= 1; 
  53.             mul_2(); 
  54.         }
  55.         return solve(); 
  56.     }
  57.     return 0;
  58. }
  59. int main() {
  60.     //freopen("na.in", "r", stdin);
  61.     //freopen("na.out", "w", stdout);
  62.     long long T;
  63.     scanf("%lld", &T);
  64.     while(T--) {
  65.         std::string s;
  66.         std::cin >> s;
  67.         long long n = 0;
  68.         for (int i = 0; i < s.length(); i++) {
  69.             n = (n * 10 + (s[i] - '0') + 329616) % 329616;
  70.         }
  71.         //printf("%lld\n", n);
  72.         long long ans1 = pow(n, 2000000016);
  73.         long long ans = pow(ans1, 1000000007);
  74.         printf("%lld\n", ans);
  75.     }
  76.     //fclose(stdin);
  77.     //fclose(stdout);
  78.     return 0;
  79. }