fork download
copy 
  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4.  
  5. #define MOD 1000000007
  6. #define ll long long int
  7.  
  8. ll a[101][101], p[101][101], m;
  9.  
  10. void mul(ll m1[101][101], ll m2[101][101]){
  11.     ll m3[101][101], m4[101][101];
  12.     ll i,j,k;
  13.     for(i=0; i<m; i++){
  14.         for(j=0; j<m; j++){
  15.             m3[i][j] = m1[i][j];
  16.             m4[i][j] = m2[i][j];
  17.             p[i][j] = 0;
  18.         }
  19.     }
  20.     for(i=0; i<m; i++){
  21.         for(j=0; j<m; j++){
  22.             for(k=0; k<m; k++){
  23.                 p[i][j] += (m3[i][k] * m4[k][j]);
  24.                 p[i][j] %= MOD;
  25.             }
  26.         }
  27.     }
  28. }
  29.  
  30. void power(ll n){
  31.     if(n==0 or n==1){
  32.         return;
  33.     }
  34.     power(n/2);
  35.     mul(p, p);
  36.     if(n%2){
  37.         mul(p, a);
  38.     }
  39. }
  40.  
  41. int main(){
  42.     //freopen("input_knpd.txt", "r", stdin);
  43.     ll t,n,i,j;
  44.     cin>>t;
  45.     while(t--){
  46.         cin>>m>>n;
  47.         ll s[m+1];
  48.         for(i=0; i<m; i++){
  49.             cin>>s[i];
  50.             s[i] += MOD;
  51.         }
  52.  
  53.         for(i=0; i<m; i++){
  54.             cin>>a[0][m-1-i];
  55.         }
  56.  
  57.         for(i=1; i<m; i++){
  58.             for(j=0; j<m; j++){
  59.                 if(i==(j+1)){
  60.                     a[i][j] = 1;
  61.                 }
  62.                 else{
  63.                     a[i][j] = 0;
  64.                 }
  65.             }
  66.         }
  67.         for(i=0; i<m; i++){
  68.             for(j=0; j<m; j++){
  69.                 p[i][j] = a[i][j];
  70.             }
  71.         }
  72.         if(n>=m){
  73.             power(n-m+1);
  74.             ll ans = 0;
  75.             for(i=0; i<m; i++){
  76.                 ans += (p[0][i]*s[m-1-i]);
  77.                 ans %= MOD;
  78.             }
  79.             cout<<ans<<endl;
  80.         }
  81.         else{
  82.             cout<<s[n]%MOD<<endl;
  83.         }
  84.     }
  85.     return 0;
  86. }
Success #stdin #stdout 0s 3508KB
comments (?)
stdin
copy 
1
2 2
0 1
0 1
stdout
copy 
1
https://ideone.com/UrYIla
language:
C++ (gcc 8.3)
created:
9 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!