Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <ctime>
- #include <cassert>
- #include <cstdio>
- #include <queue>
- #include <set>
- #include <map>
- #include <fstream>
- #include <cstdlib>
- #include <string>
- #include <cstring>
- #include <algorithm>
- #include <numeric>
- #define mp make_pair
- #define mt make_tuple
- #define fi first
- #define se second
- #define pb push_back
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
- #define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
- #define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
- #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
- using namespace std;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- typedef vector<pii> vpi;
- typedef vector<vi> vvi;
- typedef long long i64;
- typedef vector<i64> vi64;
- typedef vector<vi64> vvi64;
- template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
- template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
- vector<pair<int, vector<pii> > > ts;
- map<pair<int, vector<pii> >, int> en;
- map<pii, int> trans, wt;
- int dfs(int sp, vector<pii> mps) {
- if (sp > 2) return -1;
- for (pii p: mps) {
- if (p.fi > 2 || p.se > 2) return -1;
- if (p.fi > p.se) swap(p.fi, p.se);
- }
- sort(all(mps));
- auto t = mp(sp, mps);
- if (en.count(t)) return en[t];
- en[t] = ts.size();
- ts.pb(t);
- int n = en[t];
- // cerr << n << ' ' << sp << ' ' << mp1 << ' ' << mp2 << '\n';
- for (pii &w: mps) {
- ++w.fi; ++w.se;
- }
- ++trans[mp(n, dfs(0, mps))];
- ++wt[mp(n, dfs(sp + 1, mps))];
- mps.pb(mp(0, 0));
- ++trans[mp(n, dfs(sp + 1, mps))];
- mps.pop_back();
- forn(i, mps.size()) {
- forn(j, 2) {
- vector<pii> nmps = mps;
- nmps[i].fi = 0;
- ++trans[mp(n, dfs(sp + 1, nmps))];
- nmps = mps;
- int t = mps[i].fi;
- nmps.erase(nmps.begin() + i);
- ++trans[mp(n, dfs(t, nmps))];
- if (mps[i].fi == mps[i].se) break;
- swap(mps[i].fi, mps[i].se);
- }
- }
- return n;
- }
- const i64 P = 100000000 + 2015;
- void add(i64 &x, i64 y) {
- x += y; x %= P;
- }
- vvi64 mul(const vvi64 &a, const vvi64 &b) {
- int n = a.size();
- vvi64 c(n, vi64(n));
- forn(i, n) forn(j, n) forn(k, n) add(c[i][k], a[i][j] * b[j][k]);
- return c;
- }
- vvi64 deg(vvi64 a, i64 d) {
- int n = a.size();
- vvi64 c(n, vi64(n));
- forn(i, n) c[i][i] = 1;
- while (d) {
- if (d & 1) c = mul(c, a);
- a = mul(a, a);
- d /= 2;
- }
- return c;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.precision(10);
- cout << fixed;
- #ifdef LOCAL_DEFINE
- freopen("input.txt", "rt", stdin);
- #endif
- dfs(0, vector<pii>());
- cerr << ts.size() << '\n';
- int K = ts.size();
- vvi64 mt(K, vi64(K)), mw(K, vi64(K));
- for (auto w: trans) {
- int x = w.fi.fi, y = w.fi.se;
- if (y == -1) continue;
- mt[x][y] = w.se;
- }
- for (auto w: wt) {
- int x = w.fi.fi, y = w.fi.se;
- if (y == -1) continue;
- mw[x][y] = w.se;
- }
- i64 N, M;
- cin >> N >> M;
- vi64 a(M + 1);
- a[0] = 1;
- for1(i, M) cin >> a[i];
- vvi64 m(K, vi64(K));
- forn(i, K) m[i][i] = 1;
- forn(i, M) {
- m = mul(m, deg(mt, a[i + 1] - a[i] - 1));
- m = mul(m, mw);
- }
- m = mul(m, deg(mt, N - a.back()));
- cout << m[0][0] << '\n';
- #ifdef LOCAL_DEFINE
- cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement