Untitled

 avatar
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