fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define int long long
  6. #define fi first
  7. #define se second
  8. #define siz(x) (int)(x.size())
  9. #define all(x) x.begin(), x.end()
  10. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  11. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  12. const int mod = 1e9+7, maxN = 2e5+5;
  13.  
  14. int n, m, t, a[maxN], c[maxN], p, q, r;
  15. struct Matrix
  16. {
  17.     int n, m;
  18.     vector<vector<int>>d;
  19.     Matrix (int N, int M): n(N), m(M)
  20.     {
  21.         d.assign(n, vector<int>());
  22.         for(int i=0; i<n; i+=1) d[i].assign(m, 0);
  23.     }
  24.  
  25.     Matrix operator*(Matrix b)
  26.     {
  27.         Matrix ans(n, b.m);
  28.         for(int i=0; i<n; i+=1)
  29.         {
  30.             for(int j=0; j<b.m; j+=1)
  31.             {
  32.                 for(int k=0; k<m; k+=1)
  33.                 {
  34.                     ans.d[i][j] = (ans.d[i][j] + 1ll*d[i][k]*b.d[k][j]) % mod;
  35.                 }
  36.             }
  37.         }
  38.         return ans;
  39.     }
  40. };
  41.  
  42. Matrix mux(Matrix x, int y)
  43. {
  44.     if(y == 1) return x;
  45.     Matrix ans = mux(x, y/2);
  46.     if(y & 1) return ans * ans * x;
  47.     else return ans * ans;
  48. }
  49.  
  50. void solve()
  51. {
  52.  
  53. }
  54.  
  55. int32_t main()
  56. {
  57.     ios_base::sync_with_stdio(0); cin.tie(0);
  58.     cin>>n>>t;
  59.     for(int i=0; i<n; i+=1) cin>>a[i];
  60.     for(int i=0; i<n; i+=1) cin>>c[i];
  61.     cin>>p>>q>>r;
  62.     if(t < n)
  63.     {
  64.         cout<<a[t]<<'\n'; return 0;
  65.     }
  66.     Matrix A(n+3, n+3);
  67.     for(int i=0; i<n; i+=1) A.d[i][0] = c[i];
  68.     A.d[n][0] = p; A.d[n+1][0] = q; A.d[n+2][0] = r;
  69.  
  70.     for(int i=1; i<n; i+=1) A.d[i-1][i] = 1;
  71.     A.d[n][n] = 1;
  72.     A.d[n][n+1] = 1; A.d[n+1][n+1] = 1;
  73.     A.d[n][n+2]=A.d[n+2][n+2]=1; A.d[n+1][n+2]=2;
  74.     Matrix ans(1, n+3);
  75.     for(int i=0; i<n; i+=1)
  76.     {
  77.         ans.d[0][i] = a[n-1-i];
  78.     }
  79.     ans.d[0][n] = 1; ans.d[0][n+1] = n; ans.d[0][n+2] = n*n;
  80.     ans = ans * mux(A, t-n+1);
  81.     cout<<ans.d[0][0]<<'\n';
  82. }
  83.  
  84. // vector hang V(i) = (a[i], a[i-1], a[i-2], ..., a[i-n+1], 1, i, i^2);
  85. // can tinh V(i+1) = (a[i+1], a[i], a[i-1], ..., a[i-n+2], 1, i+1, (i+1)^2); -> ez;
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/MmHbvl
language:
C++14 (gcc 8.3)
created:
1 day 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!