Advertisement
Guest User

Untitled

a guest
Nov 6th, 2015
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <ctime>
  5. #include <cassert>
  6. #include <cstdio>
  7. #include <queue>
  8. #include <set>
  9. #include <map>
  10. #include <fstream>
  11. #include <cstdlib>
  12. #include <string>
  13. #include <cstring>
  14. #include <algorithm>
  15. #include <numeric>
  16.  
  17. #define mp make_pair
  18. #define mt make_tuple
  19. #define fi first
  20. #define se second
  21. #define pb push_back
  22. #define all(x) (x).begin(), (x).end()
  23. #define rall(x) (x).rbegin(), (x).rend()
  24. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  25. #define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
  26. #define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
  27. #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
  28.  
  29. using namespace std;
  30.  
  31. typedef pair<int, int> pii;
  32. typedef vector<int> vi;
  33. typedef vector<pii> vpi;
  34. typedef vector<vi> vvi;
  35. typedef long long i64;
  36. typedef vector<i64> vi64;
  37. typedef vector<vi64> vvi64;
  38.  
  39. template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
  40. template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
  41.  
  42. vector<pair<int, vector<pii> > > ts;
  43. map<pair<int, vector<pii> >, int> en;
  44. map<pii, int> trans, wt;
  45.  
  46. int dfs(int sp, vector<pii> mps) {
  47.     if (sp > 2) return -1;
  48.     for (pii p: mps) {
  49.         if (p.fi > 2 || p.se > 2) return -1;
  50.         if (p.fi > p.se) swap(p.fi, p.se);
  51.     }
  52.     sort(all(mps));
  53.     auto t = mp(sp, mps);
  54.     if (en.count(t)) return en[t];
  55.     en[t] = ts.size();
  56.     ts.pb(t);
  57.     int n = en[t];
  58. //    cerr << n << ' ' << sp << ' ' << mp1 << ' ' << mp2 << '\n';
  59.     for (pii &w: mps) {
  60.         ++w.fi; ++w.se;
  61.     }
  62.     ++trans[mp(n, dfs(0, mps))];
  63.     ++wt[mp(n, dfs(sp + 1, mps))];
  64.     mps.pb(mp(0, 0));
  65.     ++trans[mp(n, dfs(sp + 1, mps))];
  66.     mps.pop_back();
  67.     forn(i, mps.size()) {
  68.         forn(j, 2) {
  69.             vector<pii> nmps = mps;
  70.             nmps[i].fi = 0;
  71.             ++trans[mp(n, dfs(sp + 1, nmps))];
  72.             nmps = mps;
  73.             int t = mps[i].fi;
  74.             nmps.erase(nmps.begin() + i);
  75.             ++trans[mp(n, dfs(t, nmps))];
  76.             if (mps[i].fi == mps[i].se) break;
  77.             swap(mps[i].fi, mps[i].se);
  78.         }
  79.     }
  80.     return n;
  81. }
  82.  
  83. const i64 P = 100000000 + 2015;
  84.  
  85. void add(i64 &x, i64 y) {  
  86.     x += y; x %= P;
  87. }
  88.  
  89. vvi64 mul(const vvi64 &a, const vvi64 &b) {
  90.     int n = a.size();
  91.     vvi64 c(n, vi64(n));
  92.     forn(i, n) forn(j, n) forn(k, n) add(c[i][k], a[i][j] * b[j][k]);
  93.     return c;
  94. }
  95.  
  96. vvi64 deg(vvi64 a, i64 d) {
  97.     int n = a.size();
  98.     vvi64 c(n, vi64(n));
  99.     forn(i, n) c[i][i] = 1;
  100.     while (d) {
  101.         if (d & 1) c = mul(c, a);
  102.         a = mul(a, a);
  103.         d /= 2;
  104.     }
  105.     return c;
  106. }
  107.  
  108. int main() {
  109.     ios::sync_with_stdio(false);
  110.     cin.tie(nullptr);
  111.     cout.precision(10);
  112.     cout << fixed;
  113. #ifdef LOCAL_DEFINE
  114.     freopen("input.txt", "rt", stdin);
  115. #endif
  116.  
  117.     dfs(0, vector<pii>());
  118.     cerr << ts.size() << '\n';
  119.  
  120.     int K = ts.size();
  121.     vvi64 mt(K, vi64(K)), mw(K, vi64(K));
  122.     for (auto w: trans) {
  123.         int x = w.fi.fi, y = w.fi.se;
  124.         if (y == -1) continue;
  125.         mt[x][y] = w.se;
  126.     }
  127.  
  128.     for (auto w: wt) {
  129.         int x = w.fi.fi, y = w.fi.se;
  130.         if (y == -1) continue;
  131.         mw[x][y] = w.se;
  132.     }
  133.     i64 N, M;
  134.     cin >> N >> M;
  135.     vi64 a(M + 1);
  136.     a[0] = 1;
  137.     for1(i, M) cin >> a[i];
  138.     vvi64 m(K, vi64(K));
  139.     forn(i, K) m[i][i] = 1;
  140.     forn(i, M) {
  141.         m = mul(m, deg(mt, a[i + 1] - a[i] - 1));
  142.         m = mul(m, mw);
  143.     }
  144.     m = mul(m, deg(mt, N - a.back()));
  145.     cout << m[0][0] << '\n';
  146.  
  147. #ifdef LOCAL_DEFINE
  148.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  149. #endif
  150.     return 0;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement