fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long 
  3. #define mod 1000000000
  4. using namespace std;
  5.  
  6. ll k,i,j;
  7. vector<ll> a,b,c;
  8.  
  9. vector<vector<ll>> multiply(vector<vector<ll>> a,vector<vector<ll>> b)
  10. {
  11.     vector<vector<ll>> c(k+1,vector<ll> (k+1));
  12.     {
  13.         for(i=1;i<=k;i++)
  14.         {
  15.             for(j=1;j<=k;j++)
  16.             { 
  17.                 for(int x=1;x<=k;x++)
  18.                 {
  19.                       c[i][j]=(c[i][j]+(a[i][x]*b[x][j])%mod)%mod;
  20.                 }
  21.  
  22.             }
  23.         }
  24.     }
  25.     return c;
  26. }
  27. vector<vector<ll>> pow(vector<vector<ll>>a,ll p)
  28. {
  29.     if(p==1)
  30.     {
  31.         return a;
  32.     }
  33.     if(p&1)
  34.     {
  35.         return multiply(a,pow(a,p-1));
  36.     }
  37.     else
  38.     {
  39.         vector<vector<ll>> x=(pow(a,p/2));
  40.         return multiply(x,x);
  41.     }
  42. }
  43. int sai(ll n)
  44. {
  45.     if(n==0)
  46.     {
  47.         return 0;
  48.     }
  49.     if(n<=k)
  50.     {
  51.         return b[n-1];
  52.     }
  53.  
  54.     vector<ll> f1(k+1);
  55.     for(i=1;i<=k;i++)
  56.     {
  57.           f1[i]=b[i-1];
  58.     }
  59.     vector<vector<ll>> t(k+1,vector<ll>(k+1));
  60.  
  61.    for(i=1;i<=k;i++)
  62.    {
  63.        for(j=1;j<=k;j++)
  64.        {
  65.            if(i<k)
  66.            {
  67.                if(j==i+1)
  68.                {
  69.                    t[i][j]=1;
  70.                }
  71.                else
  72.                {
  73.                    t[i][j]=0;
  74.                }
  75.                continue;
  76.            }
  77.            t[i][j]=c[k-j];
  78.        }
  79.    }
  80.    t= pow(t,n-1);
  81.  
  82.    ll res=0;
  83.    for(i=1;i<=k;i++)
  84.    {
  85.        res=(res+(t[1][i]*f1[i])%mod)%mod;
  86.    }
  87.    return res;
  88.  
  89. }
  90. int main() {
  91.     ll t,n;
  92.  
  93.     while(t--)
  94.     {
  95.         ll num;
  96.         cin>>k;
  97.         for(i=0;i<k;i++)
  98.         {
  99.              cin>>num;
  100.              b.push_back(num);
  101.         }
  102.         for(i=0;i<k;i++)
  103.         {
  104.             cin>>num;
  105.             c.push_back(num);
  106.         }
  107.         cin>>n;
  108.         cout<<sai(n)<<endl;
  109.  
  110.         c.clear();
  111.         b.clear();
  112.     }
  113.  
  114. }
  115.  
Success #stdin #stdout 0s 4284KB
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 
Standard output is empty
https://ideone.com/xPGgIe
language:
C++ (gcc 8.3)
created:
5 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!