This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
struct hsh {
size_t operator()(const pi& k) const {
return (ll)MOD*k.f+k.s; // bad, but you get the point
}
};
int q, n, num[10];
ll m[2][3][301][301], M[2][3][301][301];
string tmp[10];
string gen(vi nex) {
int lst = -1;
string res;
for (int i: nex) {
if (i == -1) res += '-';
else if (lst != -1 && i+lst == 10) {
res += '/';
lst = -1;
} else if (i == 10) res += 'x';
else {
if (lst == -1) lst = 0;
res += char('0'+i);
lst += i;
}
}
return res;
}
bool match(string bad, vi nex) {
string t = gen(nex);
F0R(i,sz(bad)) if (bad[i] != '?' && bad[i] != t[i]) return 0;
return 1;
}
void tri(int a, int b, int c, int d, int x, vi y) {
int val = m[a][b][c][d];
int cur = d;
for (int i: y) if (i != -1) {
cur += i;
if (a) c += i, d += i, cur += i, a --;
if (b) d += i, cur += i, b --;
}
int posi = 0;
if (x != n-1) {
if (y[0] == 10) posi = 2;
else if (y[0]+y[1] == 10) posi = 1;
}
if (x >= 2 && a == 0 && num[x-2] != -1 && c != num[x-2]) return;
if (x >= 1 && b == 0 && num[x-1] != -1 && d != num[x-1]) return;
if (posi == 0 && num[x] != -1 && cur != num[x]) return;
M[b][posi][d][cur] += val;
}
void process(int x) {
vector<vi> posi;
if (x != n-1) {
if (match(tmp[x],{10,-1})) posi.pb({10,-1});
F0R(i,10) F0R(j,11-i) if (match(tmp[x],{i,j})) posi.pb({i,j});
} else {
F0R(i,11) if (match(tmp[x],{10,10,i})) posi.pb({10,10,i});
F0R(i,10) F0R(j,11-i) if (match(tmp[x],{10,i,j})) posi.pb({10,i,j});
F0R(i,10) F0R(j,11) if (match(tmp[x],{i,10-i,j})) posi.pb({i,10-i,j});
F0R(i,10) F0R(j,10-i) if (match(tmp[x],{i,j,-1})) posi.pb({i,j,-1});
}
vector<vi> POSI;
F0R(a,2) F0R(b,3) F0R(c,301) F0R(d,301)
if (m[a][b][c][d]) POSI.pb({a,b,c,d});
for (auto v: posi) for (auto V: POSI)
tri(V[0],V[1],V[2],V[3],x,v);
F0R(a,2) F0R(b,3) F0R(c,301) F0R(d,301) {
m[a][b][c][d] = M[a][b][c][d];
M[a][b][c][d] = 0;
}
}
void solve() {
cin >> n;
string s; cin >> s;
F0R(i,n-1) tmp[i] = s.substr(2*i,2);
tmp[n-1] = s.substr(2*(n-1),3);
F0R(i,n) cin >> num[i];
memset(m,0,sizeof m);
m[0][0][0][0] = 1;
F0R(i,n) process(i);
ll ans = 0;
F0R(i,301) F0R(j,301) ans += m[0][0][i][j];
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> q;
F0R(i,q) solve();
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |