fork download
copy 
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. #define rep(i,n) for (int i = 1; i <= n; i++)
  5. using namespace std;
  6.  
  7. typedef long long int ll;
  8. typedef vector<vector<ll> > matrix;
  9. const ll mod = 1000000000;
  10.  
  11. matrix mul(matrix A,matrix B,int k){
  12. matrix c(k+1,vector<ll>(k+1));
  13. for(int i=1;i<=k;i++){
  14.   for(int j=1;j<=k;j++){
  15.        for(int l=1;l<=k;l++){
  16.          c[i][j]=(c[i][j]+(A[i][l]*B[l][j]))%mod; 
  17.        }
  18.   }
  19. }
  20. return c;
  21.  
  22. }
  23.  
  24. matrix pow(matrix A,int p,int k){
  25. if(p==1)
  26. return A;
  27. if(p%2){
  28.   return mul(A,pow(A,p-1,k),k);
  29.  
  30. }
  31. matrix X=pow(A, p/2,k); 
  32. return mul(X,X,k); 
  33.  
  34. }
  35.  
  36.  
  37. int fib(int N,vector<ll>b1,vector<ll>c1,int k){
  38. vector<ll>bb(k+1);
  39.  
  40. rep(i,k){
  41.   bb[i]=b1[i];
  42. }
  43.  
  44. matrix T(k+1,vector<ll>(k+1));
  45.  
  46. for(int y=1;y<=k;y++){
  47.   for(int u=1;u<=k;u++){
  48.     if(y+1==u)
  49.     T[y][u]=1;
  50.  
  51.   }
  52. }
  53.  
  54. rep(i,k){
  55.   int y=c1.back();
  56.   c1.pop_back();
  57.   T[k][i]=y;
  58. }
  59.  
  60. if(N<k){
  61. cout<<b1[N]<<endl;
  62. return 0;
  63.  
  64.  
  65. }
  66.  
  67. T=pow(T,N-1,k);
  68.  
  69. ll res=0;
  70. for(int i=1;i<=k;i++)
  71. res=(res+T[1][i]*bb[i])%mod;
  72. cout<<res<<endl;
  73.  
  74. }
  75.  
  76. int main(){
  77.   int cas,k,b,c,n;
  78.   cin>>cas;
  79.  
  80.  
  81.   rep(i,cas)
  82.    {   
  83.  
  84.      cin>>k;
  85.        vector<ll>b1(k+1);
  86.    vector<ll>c2(k+1);
  87.  
  88.  
  89.     rep(j,k){
  90.  
  91.       cin>>b;
  92.       b1[j]=b;
  93.  
  94.     }
  95.      rep(o,k){
  96.  
  97.  
  98.         cin>>c;
  99.         c2[o]=c;
  100.       }
  101.       cin>>n;
  102.  
  103.       fib(n,b1,c2,k);
  104.  
  105.    }
  106.  
  107.  
  108. }
Runtime error #stdin #stdout #stderr 0s 4392KB
comments (?)
stdin
copy 
3 
3 
5 8 2 
32 54 6 
2 
3 
1 2 3 
4 5 6 
6 
3 
24 354 6 
56 57 465 
98765432
stdout
copy 
8
714
stderr
copy 
free(): double free detected in tcache 2
https://ideone.com/naYBuD
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!