Advertisement
kdbeatbox

Untitled

Dec 8th, 2021
467
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. /*******************************************|
  2. | Basic ass template for basic ass problems |
  3. | - Mohd Safwan                             |
  4. | https://safwankdb.github.io               |
  5. |__________________________________________*/
  6.  
  7. #pragma GCC optimize ("O3")
  8. #pragma GCC target ("avx2")
  9.  
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. #define REP(i, s, e) for (int i = (s); i < (e); i++)
  14. #define REPR(i, e, s) for (int i = (e) - 1; i >= (s); i--)
  15. #define SPEED ios_base::sync_with_stdio(0); cin.tie(0);
  16. #define endl '\n'
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef array<ll, 2> ii;
  21. template <typename T>
  22. using V = vector<T>;
  23.  
  24. const int MOD = 1e9 + 7;
  25. const int INF = 1e7 + 5;
  26. const int LOG = 32;
  27.  
  28. typedef array<array<ll, 9>, 9> Mat;  
  29.  
  30. Mat operator*(Mat &a, Mat &b) {
  31.     Mat ans = {};
  32.     REP(i, 0, 9) REP(k, 0, 9) REP(j, 0, 9) {
  33.         ans[i][j] += a[i][k] * b[k][j];
  34.     }
  35.     return ans;
  36. }
  37.  
  38. Mat Pow(Mat &a, int n) {
  39.     Mat ans = {};
  40.     REP(i, 0, 9) ans[i][i] = 1;
  41.     while (n) {
  42.         if (n & 1) ans = ans * a;
  43.         a = a * a;
  44.         n /= 2;
  45.     }
  46.     return ans;
  47. }
  48.  
  49. int main() {
  50.     SPEED
  51.     int n = 300;
  52.     V<ull> F(9, 0);
  53.     REP(i, 0, n) {
  54.         int t;
  55.         cin >> t;
  56.         F[t]++;
  57.     }
  58.     Mat M = {};
  59.     REP(i, 0, 8) M[i][i+1] = 1;
  60.     M[6][0] = 1;
  61.     M[8][0] = 1;
  62.     M = Pow(M, 256);
  63.     ull ans = 0;
  64.     REP(i, 0, 9) REP(j, 0, 9) ans += M[i][j] * F[j];
  65.     cout << ans << endl;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement