fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int lli;
  6.  
  7. #define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
  8. #define MOD (lli)1000000007
  9.  
  10. int m;
  11.  
  12. lli** mult(lli** A, lli** B)
  13. {
  14.     lli** C = (lli**)malloc(m * sizeof(lli*));
  15.     for (int i = 0; i < m; i++)
  16.         C[i] = (lli*)malloc(m * sizeof(lli));
  17.  
  18.     for (int i = 0; i < m; i++) {
  19.         for (int j = 0; j < m; j++) {
  20.             for (int k = 0; k < m; k++) {
  21.                 C[i][j] += ((A[i][k] % MOD) * (B[k][j] % MOD)) % MOD;
  22.                 if(C[i][j] > MOD) C[i][j] -= MOD;
  23.             }
  24.         }
  25.     }
  26.  
  27.     return C;
  28. }
  29.  
  30. lli** expM(lli** A, lli n)
  31. {
  32.     if (n == 1)
  33.         return A;
  34.     else if ((n % 2) == 1)
  35.         return mult(A, expM(A, n - 1));
  36.     else{
  37.     	lli** aux = expM(A, n / 2);
  38.         return mult(aux, aux);
  39.     }
  40. }
  41.  
  42. int main()
  43. {
  44.     lli n;
  45.     cin >> n >> m;
  46.  
  47.     if(n < m) printf("1\n");
  48.     else if(n == m) printf("2\n");
  49.     else{
  50.     lli** T = (lli**)malloc(m * sizeof(lli*));
  51.     for (int i = 0; i < m; i++)
  52.         T[i] = (lli*)malloc(m * sizeof(lli));
  53.     for (int i = 0; i < m; i++) {
  54.         for (int j = 0; j < m; j++)
  55.             T[i][j] = 0;
  56.     }
  57.     for (int i = 0; i < m - 1; i++)
  58.         T[i][i + 1] = 1;
  59.     T[m - 1][0] = 1;
  60.     T[m - 1][m - 1] = 1;
  61.  
  62.     lli** expT = expM(T, n - 1);
  63.  
  64.     lli ans = 0;
  65.  
  66.     for (int j = 0; j < m - 1; j++) {
  67.         ans += expT[0][j];
  68.         if(ans > MOD) ans -= MOD;
  69.     }
  70.     ans += (expT[0][m-1]%MOD + expT[0][m-1]%MOD)%MOD;
  71.     if(ans > MOD) ans -= MOD;
  72.  
  73.     printf("%lld\n", ans);    	
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0.52s 24344KB
comments (?)
stdin
copy 
288230376151711743 100
stdout
copy 
626842151
https://ideone.com/06XC7N
language:
C++14 (gcc 8.3)
created:
5 years 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!