Untitled
unknown
plain_text
a year ago
1.3 kB
26
Indexable
#include <iostream> #include <vector> #include <ctime> #include <algorithm> #include <assert.h> #include <map> using namespace std; #define mp make_pair const int N = 300010; #define pb push_back #define ll long long map <pair<int, vector<int> >, int> dp; int n, m; bool used[N]; int solve(int pos, vector <int> v) { auto it = dp.find(mp(pos, v)); if (it != dp.end()) return it->second; if (pos >= n) return dp[mp(pos, v)] = 1; int res = 0; for (int i = 1; i <= 8; i++) { if (!used[i]) continue; vector <int> vnew = v; if (vnew[i - 1] + 1 < i) continue; for (int j = 0; j < 8; j++) vnew[j] = min(v[j] + 1, j); vnew[i - 1] = 0; res += solve(pos + 1, vnew); if (res >= (int)(1e9+7)) res -= (int)(1e9+7); } return dp[mp(pos, v)] = res; } void Solve() { cin >> n >> m; for (int i = 1; i <= m; i++) { int x; cin >> x; used[x] = 1; } vector <int> v; for (int i = 0; i < 8; i++) v.pb(i); cout << solve(0, v) << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tests; //cin >> tests; tests = 1; while (tests--) { Solve(); } return 0; }
Editor is loading...
Leave a Comment