Untitled

unknown
plain_text
a month ago
1.3 kB
23
Indexable
Never
```#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;
}```