fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
  6.  
  7. const int mod = 1e9 + 7;
  8. struct Matrix {
  9.     vector<vector<int>> M;
  10.     int m, n;
  11.  
  12.     auto & operator [] (int i) {
  13.         return M[i];
  14.     }
  15.  
  16.     Matrix(int _m, int _n) {
  17.         m = _m; n = _n;
  18.         M = vector<vector<int>>(m, vector<int>(n, 0));
  19.     }
  20.     Matrix(vector<vector<int>> _M) {
  21.         M = _M;
  22.         m = M.size();
  23.         n = M[0].size();
  24.     }
  25.  
  26.     friend ostream & operator << (ostream &out, const Matrix &d) {
  27.         for (auto x : d.M) {
  28.             for (auto y : x) out << y << ' ';
  29.             out << '\n';
  30.         }
  31.         return out;
  32.     }
  33. };
  34.  
  35. Matrix Identity(int x) {
  36.     Matrix C(x, x);
  37.     for (int i = 0; i < x; i++) C.M[i][i] = 1;
  38.     return C;
  39. }
  40.  
  41. Matrix operator *(Matrix A, Matrix B) {
  42.     assert(A.n == B.m);
  43.  
  44.     Matrix C(A.m, B.n);
  45.     for (int i = 0; i < A.m; i++) {
  46.         for (int j = 0; j < B.n; j++) {
  47.             int sum = 0;
  48.             for (int k = 0; k < A.n; k++) {
  49.                 sum += A.M[i][k] * B.M[k][j];
  50.                 sum %= mod;
  51.             }
  52.             C.M[i][j] = sum;
  53.         }
  54.     }
  55.     return C;
  56. }
  57.  
  58. Matrix powpow(Matrix A, int y) {
  59.     assert(A.n == A.m);
  60.  
  61.     Matrix res = Identity(A.n);
  62.     for (; y > 0; y >>= 1) {
  63.         if (y&1) res = res*A;
  64.         A = A*A;
  65.     }
  66.     return res;
  67. }
  68.  
  69.  
  70. int powmod(int a, int b) {
  71.     int res = 1;
  72.     for (; b > 0; b >>= 1) {
  73.         if (b&1) res = (res*a) % mod;
  74.         a = (a*a) % mod;
  75.     }
  76.     return res;
  77. }
  78.  
  79. const int maxn = 11;
  80. int n1, m, arr[maxn];
  81.  
  82. int n = 0;
  83.  
  84. int32_t main() {
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(nullptr);
  87.     fileio("");
  88.     // freopen("debug.txt", "w", stderr);
  89.  
  90.     cin >> n1 >> m;
  91.     vector<pair<int, int>> E;
  92.     for (int i = 1; i <= n1; i++) {
  93.         cin >> arr[i];
  94.         for (int j = 1; j < arr[i]; j++) {
  95.             E.push_back({n+j, n+j+1});
  96.         }
  97.         E.push_back({n+arr[i], n+1});
  98.         if (i > 1) {
  99.             E.push_back({n-arr[i-1]+1, n+1});
  100.         }
  101.         n += arr[i];
  102.     }
  103.  
  104.     Matrix C(n, n), A(1, n); A[0][0] = 1;
  105.     for (auto e: E) {
  106.         int u = e.first - 1, v = e.second - 1;
  107.         C[u][v]++;
  108.     }
  109.  
  110.     A = A * powpow(C, n1-1) * powpow(C, m);
  111.  
  112.     cout << A[0][n-arr[n1]];
  113.  
  114.     return 0 ^ 0;
  115. }
  116.  
Runtime error #stdin #stdout 0.01s 5388KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/XJAY8T
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 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!