fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 105
  5. #define mod 1000000007
  6. ll n, k, i, j, x, res, tmp, ans;
  7. ll freq[maxn];
  8. struct matran
  9. {
  10.         ll a[101][101];
  11.         void print()
  12.         {
  13.                 for (ll i = 0; i < 101; i++)
  14.                 {
  15.                         for (ll j = 0; j < 101; j++)
  16.                                 cout << a[i][j] << " ";
  17.                         cout << '\n';
  18.                 }
  19.         }
  20. };
  21. struct matran_1
  22. {
  23.         ll a[1][101];
  24.         void print()
  25.         {
  26.                 for (ll i = 0; i < 1; i++)
  27.                 {
  28.                         for (ll j = 0; j < 101; j++)
  29.                                 cout << a[i][j] << " ";
  30.                         cout << '\n';
  31.                 }
  32.         }
  33. };
  34. matran mot, M;
  35. matran_1 init, ress;
  36. matran prod(matran A, matran B)
  37. {
  38.         matran C;
  39.         for (ll i = 0; i < 101; i++)
  40.                 for (ll j = 0; j < 101; j++)
  41.                         C.a[i][j] = 0;
  42.         for (ll i = 0; i < 101; i++)
  43.                 for (ll j = 0; j < 101; j++)
  44.                         for (ll k = 0; k < 101; k++)
  45.                                 C.a[i][j] = (C.a[i][j] + A.a[i][k] % mod * B.a[k][j] % mod) % mod;
  46.         return C;
  47. }
  48. matran_1 prod1(matran_1 A, matran B)
  49. {
  50.         matran_1 C;
  51.         for (ll i = 0; i < 1; i++)
  52.                 for (ll j = 0; j < 101; j++)
  53.                         C.a[i][j] = 0;
  54.         for (ll i = 0; i < 1; i++)
  55.                 for (ll j = 0; j < 101; j++)
  56.                         for (ll k = 0; k < 101; k++)
  57.                                 C.a[i][j] = (C.a[i][j] + A.a[i][k] % mod * B.a[k][j] % mod) % mod;
  58.         return C;
  59. }
  60. matran po(matran A, ll n)
  61. {
  62.         matran res = A, ans = mot;
  63.         while (n)
  64.         {
  65.                 if (n % 2)
  66.                         ans = prod(ans, res);
  67.                 res = prod(res, res);
  68.                 n /= 2;
  69.         }
  70.         return ans;
  71. }
  72.  
  73. int main()
  74. {
  75.  
  76.  
  77.         cin >> n >> k;
  78.         for (i = 0; i < n; i++)
  79.         {
  80.                 cin >> x;
  81.                 freq[x]++;
  82.         }
  83.         for (ll i = 0; i < 101; i++)
  84.                 for (ll j = 0; j < 101; j++)
  85.                         if (i == j)
  86.                                 mot.a[i][j] = 1;
  87.                         else
  88.                                 mot.a[i][j] = 0;
  89.         for (ll i = 0; i < 101; i++)
  90.                 for (ll j = 0; j < 101; j++)
  91.                 {
  92.                         if (j == 0 && (i <= 1))
  93.                                 M.a[i][j] = 1;
  94.                         else if (j == 0 && (i > 1))
  95.                                 M.a[i][j] = 0;
  96.                         if (j == 1 && i == 0)
  97.                                 M.a[i][j] = 0;
  98.                         else if (j == 1 && i > 0)
  99.                                 M.a[i][j] = freq[i];
  100.                         if (j >= 2)
  101.                         {
  102.                                 if (j - i == 1)
  103.                                         M.a[i][j] = 1;
  104.                                 else
  105.                                         M.a[i][j] = 0;
  106.                         }
  107.                 }
  108.         for (i = 0; i < 1; i++)
  109.                 for (j = 0; j < 101; j++)
  110.                 {
  111.                         if (j == 0)
  112.                                 init.a[i][j] = 0;
  113.                         if (j == 1)
  114.                                 init.a[i][j] = 1;
  115.                         if (j > 1)
  116.                                 init.a[i][j] = 0;
  117.                 }
  118.         ress = prod1(init, po(M, k+1));
  119.         cout << ress.a[0][0]<<'\n';
  120.         // for(i=1;i<=5;i++) cout<<freq[i]<<" ";
  121.         // cout<<'\n';
  122.         // init.print();
  123.         // cout<<"-----\n";
  124.         // M.print();
  125.         // cout<<"------\n";
  126.         // po(mot,3).print();
  127.         // cout<<'\n';
  128.         return 0;
  129. }
Success #stdin #stdout 0.02s 4640KB
comments (?)
stdin
copy 
3 3 
1 2 3
stdout
copy 
8
https://ideone.com/CIwRAy
language:
C++ (gcc 8.3)
created:
3 years 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!