fork download 
  1. #include<bits/stdc++.h>
  2. #define file "fibosum"
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define pii pair<int,int>
  8. #define vi vector<int>
  9. #define pb push_back
  10. #define mp make_pair
  11. #define X first
  12. #define Y second
  13. #define vii vector<vector<int>>
  14.  
  15. const int N=1e6+5;
  16. const int NN=1e3+9;
  17. const int MOD=1e9+7;
  18. const int INF=1e18;
  19.  
  20. int n;
  21. vii dp(4, vector<int> (4, 0));
  22.  
  23. int nhan(int a, int b) {
  24.     if (b==0) return 0;
  25.     if (b==1) return a;
  26.     int tmp=nhan(a,b/2)%MOD;
  27.     if (b&1)
  28.         return (((tmp+tmp)%MOD)+a)%MOD;
  29.     return (tmp+tmp)%MOD;
  30. }
  31.  
  32. vii mul(const vii& a, const vii& b) {
  33.     vii res(4, vector<int> (4, 0));
  34.     for (int i=1;i<=3;i++)
  35.     for (int j=1;j<=3;j++)
  36.     for (int k=1;k<=3;k++) {
  37.         res[i][j]+=(nhan(a[i][k],b[k][j]))%MOD;
  38.         res[i][j]%=MOD;
  39.     }
  40.     return res;
  41. }
  42.  
  43. void inkq(const vii& a) {
  44.     for (int i=1;i<=3;i++) {
  45.         for (int j=1;j<=3;j++)
  46.             cout<<a[i][j]<<" ";
  47.         cout<<endl;
  48.     }
  49. }
  50.  
  51. vii pow(const vii& a, int b) {
  52.     if (b==1) return a;
  53.     vii tmp=pow(a,b/2);
  54.     if (b&1)
  55.         return mul(mul(tmp,tmp),a);
  56.     return mul(tmp,tmp);
  57. }
  58.  
  59. void process() {
  60.     cin>>n;
  61.     vii t(4, vector<int> (4, 0));
  62.     t={
  63.         {0, 0, 0, 0},
  64.         {0, 1, 1, 1},
  65.         {0, 0, 1, 1},
  66.         {0, 0, 1, 0}
  67.     };
  68.     dp=pow(t,n+1);
  69. //    inkq(dp);
  70.     cout<<dp[1][3];
  71. }
  72.  
  73. signed main() {
  74.     cin.tie(0)->sync_with_stdio(0);
  75.  
  76.     int t=1;
  77. //    cin>>t;
  78.     while (t--)
  79.         process();
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
100000000
stdout 
799162515
https://ideone.com/LN5N1e
language:
C++14 (gcc 8.3)
created:
3 days 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!