fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MOD_P   = 998244353;
  5. const long long MOD_PHI = 998244352; // p - 1
  6.  
  7. using Matrix = array<array<long long, 2>, 2>;
  8.  
  9. Matrix mat_mul(const Matrix& a, const Matrix& b, long long m) {
  10.     Matrix c = {{{0, 0}, {0, 0}}};
  11.     for (int i = 0; i < 2; i++)
  12.         for (int k = 0; k < 2; k++)
  13.             if (a[i][k])
  14.                 for (int j = 0; j < 2; j++)
  15.                     c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
  16.     return c;
  17. }
  18.  
  19. Matrix mat_pow(Matrix mat, long long exp, long long m) {
  20.     Matrix result = {{{1, 0}, {0, 1}}}; // identity
  21.     while (exp > 0) {
  22.         if (exp & 1) result = mat_mul(result, mat, m);
  23.         mat = mat_mul(mat, mat, m);
  24.         exp >>= 1;
  25.     }
  26.     return result;
  27. }
  28.  
  29. // Fibonacci(n) mod m using matrix exponentiation
  30. // Fib(0)=0, Fib(1)=1, Fib(2)=1, ...
  31. long long fib_mod(long long n, long long m) {
  32.     if (m == 1) return 0;
  33.     if (n == 0) return 0;
  34.     Matrix base = {{{1, 1}, {1, 0}}};
  35.     return mat_pow(base, n, m)[0][1];
  36. }
  37.  
  38. long long pow_mod(long long base, long long exp, long long m) {
  39.     long long result = 1;
  40.     base %= m;
  41.     while (exp > 0) {
  42.         if (exp & 1) result = result * base % m;
  43.         base = base * base % m;
  44.         exp >>= 1;
  45.     }
  46.     return result;
  47. }
  48.  
  49. int main() {
  50.     ios::sync_with_stdio(false);
  51.     cin.tie(nullptr);
  52.  
  53.     long long n;
  54.     cin >> n;
  55.  
  56.     // F(n) = 2^Fib(n)
  57.     // By Fermat's little theorem: 2^x mod p = 2^(x mod (p-1)) mod p
  58.     long long fib_n = fib_mod(n, MOD_PHI);
  59.     cout << pow_mod(2, fib_n, MOD_P) << "\n";
  60. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
849110189
https://ideone.com/Lz0UG4
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!