#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define all(v) begin(v), end(v)
using ll = long long;
void solve();
int main() {
int q; cin >> q;
rep (_, q) solve();
}
void solve() {
int n; cin >> n;
string s; cin >> s;
vector<int> a(n);
rep (i, n) cin >> a[i];
vector dp(n, vector(301, vector(11, vector(11, 0ll))));
// dp[i][j][k][l] : i までやって現在の得点が j で、次の二回の shot で k, l 本倒す方法の数
rep (i, 11) rep (j, 11) dp[0][0][i][j] = 1;
rep (i, n - 1) {
string t = s.substr(i * 2, 2);
rep (j, 301) rep (k, 11) rep (l, 11) {
if (dp[i][j][k][l] == 0) continue;
if (k == 10) {
if ((t[0] == 'x' || t[0] == '?') && (t[1] == '-' || t[1] == '?')) {
rep (m, 11) {
if (a[i] == -1 || a[i] == j + 10 + l + m) dp[i + 1][j + 10 + l + m][l][m] += dp[i][j][k][l];
}
}
}
else {
if (t[0] == 'x' || t[1] == '-') continue;
if (k + l == 10) {
if (t[1] == '/' || t[1] == '?') {
if (t[0] != '?' && t[0] - '0' != k) continue;
rep (m, 11) {
if (a[i] == -1 || a[i] == j + 10 + m) {
rep (n, 11) dp[i + 1][j + 10 + m][m][n] += dp[i][j][k][l];
}
}
}
}
else {
if (t[1] == '/') continue;
if (t[0] != '?' && t[0] - '0' != k) continue;
if (t[1] != '?' && t[1] - '0' != l) continue;
if (a[i] == -1 || a[i] == j + k + l) {
rep (m, 11) rep (n, 11) dp[i + 1][j + k + l][m][n] += dp[i][j][k][l];
}
}
}
}
}
ll ans = 0;
string t = s.substr((n - 1) * 2);
rep (s, 301) {
do {
if (t[0] != '?' && t[0] != 'x') continue;
if (t[1] != '?' && t[1] != 'x') continue;
if (t[2] != '?' && t[2] != 'x') continue;
if (a[n - 1] == -1 || a[n - 1] == s + 30) ans += dp[n - 1][s][10][10];
} while (0);
rep (i, 10) {
if (t[0] != '?' && t[0] != 'x') continue;
if (t[1] != '?' && t[1] != 'x') continue;
if (t[2] != '?' && t[2] - '0' != i) continue;
if (a[n - 1] == -1 || a[n - 1] == s + 20 + i) ans += dp[n - 1][s][10][10];
}
rep (i, 10) {
if (t[0] != '?' && t[0] != 'x') continue;
if (t[1] != '?' && t[1] - '0' != i) continue;
if (t[2] != '?' && t[2] != '/') continue;
if (a[n - 1] == -1 || a[n - 1] == s + 20) ans += dp[n - 1][s][10][i];
}
rep (i, 10) rep (j, 10) {
if (i + j >= 10) break;
if (t[0] != '?' && t[0] != 'x') continue;
if (t[1] != '?' && t[1] - '0' != i) continue;
if (t[2] != '?' && t[2] - '0' != j) continue;
if (a[n - 1] == -1 || a[n - 1] == s + i + j) ans += dp[n - 1][s][10][i];
}
rep (i, 10) {
if (t[0] != '?' && t[0] - '0' != i) continue;
if (t[1] != '?' && t[1] != '/') continue;
if (t[2] != '?' && t[2] != 'x') continue;
if (a[n - 1] == -1 || a[n - 1] == s + 20) ans += dp[n - 1][s][i][10 - i];
}
rep (i, 10) rep (j, 10) {
if (t[0] != '?' && t[0] - '0' != i) continue;
if (t[1] != '?' && t[1] != '/') continue;
if (t[2] != '?' && t[2] - '0' != j) continue;
if (a[n - 1] == -1 || a[n - 1] == s + 10 + j) ans += dp[n - 1][s][i][10 - i];
}
rep (i, 10) rep (j, 10) {
if (i + j >= 10) break;
if (t[0] != '?' && t[0] - '0' != i) continue;
if (t[1] != '?' && t[1] - '0' != j) continue;
if (t[2] != '?' && t[2] != '-') continue;
if (a[n - 1] == -1 || a[n - 1] == s + i + j) ans += dp[n - 1][s][i][j];
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
