The subproblem—when \(x\) is 000000

In this subproblem, the range of \(s\) of interest is those \(s\) such that \(s_k \leq y_k\) for all \(k\).

We will find the answer for all \(10^6\) values for \(y\). This can be found with a cumulative-sum algorithm extended to \(6\) dimensions.

Let \(\mathrm{zeta}_m[y]\) be the sum of sizes of \(s\) for all \(s\) such that:

• \(s_k \leq y_k\)for all \(k \leq m\).
• \(s_k = y_k\) for all \(k > m\).

\(\mathrm{zeta}_0[y]\) corresponds to \(s = y\), and \(\mathrm{zeta}_6[y]\) corresponds to the sought answer.

Then, one can find \(\mathrm{zeta}_{m}\) based on \(\mathrm{zeta}_{m-1}\) using the following cumulative sums:

• In ascending order of \(y\), compute as follows:
  • if the \(k\)-th digit of \(y\) is 0, let \(\mathrm{zeta}_m[y] = \mathrm{zeta}_{m-1}[y]\).
  • If the \(k\)-th digit of \(y\) is not 0, let \(\mathrm{zeta}_m[y] = \mathrm{zeta}_m[y'] + \mathrm{zeta}_{m-1}[y]\), where \(y'\) is the \(k\)-th digit of \(y\) subtracted by \(1\).

By performing this for \(m=1,\dots,6\), the answer can be found for all \(y\).

Reducing original problem to subproblem

If there exists \(k\) with \(x_k > y_k\), the answer is \(0\). We assume that there is none.

The range of \(s\) of interest is \(s_k \leq y_k\) for all \(k\), with the following additional six conditions imposed:

• condition \(c_1\): \(s_1 \leq x_1 - 1\) does not hold.
• condition \(c_2\): \(s_2 \leq x_2 - 1\) does not hold.
• \(\vdots\)
• condition \(c_6\): \(s_6 \leq x_6 - 1\) does not hold.

For a subset \(T\) of the six conditions \(\{c_1,c_2,\dots,c_6\}\), let \(F(T)\) be “the range of \(s\) that violates the conditions in \(T\), while whether the other conditions are satisfied is ignored,” and \(g(T)\) be the total size for the IDs belonging to \(F(T)\). Then by the Inclusion-Exclusion Principle, the sought value turns out equal to:

\[\sum_{T \subseteq \{c_1,\dots,c_6\} } (-1)^{|T|} g(T)\]

For each \(T\), the range represented by \(F(T)\) is “the \(s\) satisfying \(s_k \leq \begin{cases} y_k & (c_k \notin T) \\ x_k - 1 & (c_k \in T) \end{cases}\) for all \(k\),” which is in the same form as the range mentioned in the subproblem. Therefore, the precalculated values can be directed used.

The time complexity is \(O(D \cdot N + B^D D)\) for the precalculation and \(O(2^D D)\) per query, where \(B=10,\ D=6\).

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
#include <string>
using std::string;
using std::to_string;

typedef long long int ll;

const ll BITLEN = 6;
const ll BASE = 10;
vector<ll> make_pow (ll base, ll maxv) {
	vector<ll> ans(maxv+1, 0);
	ans[0] = 1;
	for (ll i = 1; i <= maxv; i++) {
		ans[i] = ans[i-1] * base;
	}
	return ans;
}
const vector<ll> pow10 = make_pow(BASE, BITLEN);

ll idtoidx (const string s) {
	ll x = 0;
	for (ll i = 0; i < BITLEN; i++) {
		x += (ll)(s[i] - '0') * pow10[i];
	}
	return x;
}
inline ll idxdigit (const ll x, const ll d) {
	return (x / pow10[d]) % BASE;
}

void output (const ll x) {
	cout << x << "\n";
}

ll n;
vector<string> s;
vector<ll> v;
ll q;

void solve () {
	vector<ll> zeta(pow10[BITLEN], 0);
	for (ll i = 0; i < n; i++) {
		zeta[idtoidx(s[i])] += v[i];
	}
	for (ll bi = 0; bi < BITLEN; bi++) {
		for (ll i = 0; i < pow10[BITLEN]; i++) {
			if (idxdigit(i, bi) > 0) {
				zeta[i] += zeta[i - pow10[bi]];
			}
		}
	}

	cin >> q;
	for (ll qi = 0; qi < q; qi++) {
		string sx, sy;
		cin >> sx >> sy;
		ll vx = idtoidx(sx);
		ll vy = idtoidx(sy);

		ll ans = 0;
		vector<ll> wx(BITLEN), wy(BITLEN);
		bool isnonzero = true;
		for (ll i = 0; i < BITLEN; i++) {
			wx[i] = idxdigit(vx, i);
			wy[i] = idxdigit(vy, i);

			if (wx[i] > wy[i]) isnonzero = false;
		}
		if (!isnonzero) {
			ans = 0;
			output(ans);
			continue;
		}

		for (ll bi = 0; !(bi >> BITLEN); bi++) {
			ll zidx = 0;
			ll bcnt = 0;
			bool isok = true;
			for (ll i = 0; i < BITLEN; i++) {
				if (bi & (1LL << i)) {
					// -
					bcnt += 1;
					if (wx[i] <= 0) isok = false;
					zidx += (wx[i] - 1) * pow10[i];
				} else {
					// +
					bcnt += 0;
					zidx += wy[i] * pow10[i];
				}
			}
			if (!isok) continue;

			if (bcnt % 2 == 0) {
				ans += zeta[zidx];
			} else {
				ans -= zeta[zidx];
			}
		}

		output(ans);
	}

	return;
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n;
	s.resize(n);
	v.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> s[i] >> v[i];
	}
	
	solve();

	return 0;
}