Submission #374002

---

Source Code Expand

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <cstdio>
#include <bitset>

using namespace std;
typedef long long ll;

const ll MD = 1e9+7;
#define int long long

ll comb[1000][1000];
void init() {
    comb[0][0] = 1;
    for (int i = 1; i < 1000; i++) {
        comb[i][0] = 1;
        for (int j = 1; j < 1000; j++) {
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
            comb[i][j] %= MD;
        }
    }
}

int P;
int qs;
int first[200];

int data[200];
int maxd[200];

ll ddfs(int p, int q) {
    if (p == P+1) {
        if (!q) return 1;
        return 0;
    }
    if (q < 0) return 0;
    ll res = 0;
    assert(0 <= data[p] && data[p] <= maxd[p]);
    if (data[p] == maxd[p]) {
        for (int i = maxd[p]-first[p]; i <= q; i++) {
            res += ddfs(p+1, q-i) * comb[q][i];
            res %= MD;
        }
        return res;
    }
    assert(data[p] >= first[p]);
    int u = data[p] - first[p];
    return comb[q][u]*ddfs(p+1, q-u) % MD;
}

ll calc() {
    return ddfs(1, qs);        
}


int X;

int dp[15][15];

int dfs(int p, int x) {
    int res = 0;
    if (p == P+1) {
        if (!x) return 1;
        return 0;
    }
    if (x < 0) return 0;
    assert(0 <= p && p < 15);
    assert(0 <= x && x < 15);
    if (dp[p][x] != -1) return dp[p][x];
    for (int i = 0; i <= data[p]; i++) {
        res += dfs(p+1, x-p*i) * ((i == data[p] || i == 0) ? 1 : 2);
        res = min<int>(res, 2);
    }
    return dp[p][x] = res;
}

bool can() {
    memset(dp, -1, sizeof(dp));
    return dfs(1, X) == 1;
}


ll mdfs(int p) {
    if (p == P+1) {
        if (!can()) return 0;
//        for (int i = 1; i <= P; i++) {
//            printf("%d ", data[i]);
//        } printf("endprint calc:%lld\n", calc());
        return calc();
    }
    ll res = 0;
    for (int i = first[p]; i <= maxd[p]; i++) {
        data[p] = i;
        res += mdfs(p+1);
        res %= MD;
    }
    return res;
}
signed main() {
    init();
    int n;
    cin >> n >> X >> P;
    assert(1 <= n && n <= 50);
    assert(1 <= X && X <= 10);
    assert(1 <= P && P <= 10);
    for (int i = 1; i <= 15; i++) {
        maxd[i] = X/i+1;
    }
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "?") {
            qs++;
        } else if (s.size() == 2) {
            first[10]++;
        } else {
            first[s[0] - '0']++;
        }
    }
    if (first[0]) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= 15; i++) {
        first[i] = min(first[i], maxd[i]);
    }
    ll res = mdfs(1);
    cout << res << endl;
    return 0;
}

Submission Info

Judge Result