ccbeginner

TIOJ 2005

Mar 4th, 2020
112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //TIOJ 2005
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5.  
  6. int cur[3][3];
  7. int uni[3][3] = {{1,0,0},{1,1,0},{0,1,1}};
  8. int m;
  9.  
  10. void self(){
  11.     int des[3][3] = {{0}};
  12.     for(int i = 0; i < 3; ++i){
  13.         for(int j = 0; j < 3; ++j){
  14.             for(int k = 0; k < 3; ++k){
  15.                 des[i][j] += cur[i][k] * cur[k][j];
  16.                 des[i][j] %= m;
  17.             }
  18.         }
  19.     }
  20.     memcpy(cur, des, sizeof(cur));
  21. }
  22.  
  23. void mode(){
  24.     int des[3][3] = {{0}};
  25.     for(int i = 0; i < 3; ++i){
  26.         for(int j = 0; j < 3; ++j){
  27.             for(int k = 0; k < 3; ++k){
  28.                 des[i][j] += cur[i][k] * uni[k][j];
  29.                 des[i][j] %= m;
  30.             }
  31.         }
  32.     }
  33.     memcpy(cur, des, sizeof(cur));
  34. }
  35.  
  36. void matmi(int n){
  37.     if(n == 1){
  38.         memcpy(cur, uni, sizeof(cur));
  39.     }else if(n & 1){
  40.         matmi(n / 2);
  41.         self();
  42.         mode();
  43.     }else{
  44.         matmi(n / 2);
  45.         self();
  46.     }
  47. }
  48.  
  49. int32_t main(){
  50.     int n;
  51.     while(cin >> n >> m){
  52.         uni[0][0] = 1;
  53.         int ans = 0;
  54.         int dig = 0;
  55.         while(uni[0][0] <= n){
  56.             ++dig;
  57.             uni[0][0] *= 10;
  58.             int down = uni[0][0] / 10 - 1;
  59.             int up = min(uni[0][0] - 1, n);
  60.             matmi(up-down);
  61.             /*for(int i = 0; i < 3; ++i){
  62.                 for(int j = 0; j < 3; ++j){
  63.                     cout << cur[i][j] << ' ';
  64.                 }
  65.                 cout << endl;
  66.             }*/
  67.             ans = cur[0][0] * (ans) % m + cur[1][0] * (down+1) % m + cur[2][0];
  68.             ans %= m;
  69.         }
  70.         cout << ans << '\n';
  71.     }
  72.     return 0;
  73. }
  74.  
  75.  
  76. /*
  77. F(n) = F(n-1) * 10 + n
  78. F(0) = 0;
  79. F(1) = 1;
  80.  
  81.                 10      0    0
  82.                 1       1    0
  83.                 0       1    1
  84. F(n-1)  n 1  =  F(n)   n+1   1
  85. */
RAW Paste Data