fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll mod=1e9+7,n;
  5. struct matrix
  6. {
  7.     ll x[5][5];
  8.     int h,c;
  9. } a;
  10. int m;
  11. matrix mul(matrix A, matrix B)
  12. {
  13.     matrix C;
  14.     C.h=A.h;
  15.     C.c=B.c;
  16.     for(int i=1;i<=C.h;i++){
  17.         for(int j=1;j<=B.c;j++){
  18.             C.x[i][j]=0;
  19.             for(int k=1;k<=A.c;k++){
  20.                 C.x[i][j]=(C.x[i][j]  + A.x[i][k] * B.x[k][j]%mod)%mod;
  21.             }
  22.         }
  23.     }
  24.     return C;
  25. }
  26. matrix pow(matrix A, ll N)
  27. {
  28.     if(N==1) return A;
  29.     matrix temp=pow(A,N/2);
  30.     temp=mul(temp,temp);
  31.     if(N%2==1) temp=mul(temp,A);
  32.     return temp;
  33. }
  34. ll get(ll n) {
  35.     if(n==1)
  36.     {
  37.         return 1;
  38.     }
  39.     matrix a;
  40.     a.h=1;
  41.     a.c=2;
  42.     a.x[1][1]=1;
  43.     a.x[1][2]=1;
  44.  
  45.     matrix b;
  46.     b.h=2;
  47.     b.c=2;
  48.     b.x[1][1]=0;
  49.     b.x[1][2]=1;
  50.     b.x[2][1]=1;
  51.     b.x[2][2]=1;
  52.  
  53.     b=pow(b,n-1);
  54.     a=mul(a,b);
  55.  
  56.     return a.x[1][1];
  57. }
  58. int main()
  59. {
  60.     // for(int i=1;i<=1000000;i++){
  61.     //     dp[i] = dp[i-1] + get(i);
  62.     // }
  63.     while(cin>>n>>m) {
  64.         cout<<get(m+2)-get(n+1)<<'\n';
  65.     }
  66.     return 0;
  67. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qH8E4X
language:
C++14 (gcc 8.3)
created:
13 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!