Suppose that we can compute the answers for all prefixes of the input array in $T$ time. Then computing the answer for all contiguous subarrays of the input array can be done in $O(NT)$ time, and answering the queries takes $O(Q)$ additional time.
For all subtasks, we use dynamic programming.
Subtask 1: $T=O(NB)$
For each $i\in [0,N]$ and $x\in [0,B]$, let $dp[i][x]$ denote the number of ways to form $x$ after moving over papers $1\dots i$. The answer for the prefix $1\dots i$ is $\sum_{j=A}^Bdp[i][j]$.
Next, we describe how to compute all of these DP states. We initialize $dp[0][0]=1$ and use the following reasoning to generate $dp[i]$ from $dp[i-1]$. Suppose our pile currently has size $s$, has value $k$ when read from top to bottom, and that the cows are considering adding digit $a_i$ to the pile.
Since each DP transition runs in constant time, computing all these DP states takes time proportional to the number of DP states, which is $O(NB)$.
Jesse Choe's code:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int countDigits(int x) {
int ans = 0;
while (x) { ans++, x /= 10; }
return ans;
}
int main() {
int n;
long long a, b;
cin >> n >> a >> b;
int dp[n][n + 1][b + 1]{};
vector<int> d(n);
for (int i = 0; i < n; i++) cin >> d[i];
for (int i = 0; i < n; i++) { dp[i][i][0] = 1; }
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = 0; k <= b; k++) {
dp[i][j + 1][k] += dp[i][j][k], dp[i][j + 1][k] %= MOD;
int addRight = 10 * k + d[j];
if (addRight <= b) {
dp[i][j + 1][addRight] += dp[i][j][k];
dp[i][j + 1][addRight] %= MOD;
}
int addLeft = pow(10, countDigits(k)) * d[j] + k;
if (addLeft <= b) {
dp[i][j + 1][addLeft] += dp[i][j][k];
dp[i][j + 1][addLeft] %= MOD;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = 1; k <= b; k++) dp[i][j][k] += dp[i][j][k - 1];
}
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
--l;
cout << (dp[l][r][b] - dp[l][r][a - 1] + MOD) % MOD << endl;
}
}
Subtask 2: $A=B$, $T=O(N(\log_{10}B)^2)$
Let $d$ be the number of digits in $B$. For each $i\in [1,N]$ and $1\le l\le r\le d$, let $dp[i][l][r]$ denote the number of ways to form $B_{l\dots r}$ (the integer formed by concatenating the $l$th through $r$th digits of $B$) after moving over papers $1\dots i$. There are $O(Nd^2)$ such states, each of which can be computed in $O(1)$ time from $dp[i-1][l][r]$, $dp[i-1][l+1][r]$, and $dp[i][l][r-1]$. The answer for prefix $1\dots i$ is $dp[i][1][d]$.
Full credit: $T=O(N(\log_{10}B)^2)$
We subtract the number of ways to form an integer at most $A-1$ from the number of ways to form an integer at most $B$. To count the number of ways to form an integer at most $B$, we augment our DP states from the previous subtask with an additional flag that is equal to $0$, $1$, or $2$. Then $dp[i][l][r][0]$, $dp[i][l][r][1]$, and $dp[i][l][r][2]$ denote the number of ways to form an $r-l+1$-digit integer less than, equal to, or greater than $B_{l\dots r}$ after moving over papers $1\dots i$, respectively. The DP transitions are similar to the previous subtask. The answer for prefix $1\dots i$ is $dp[i][1][d][1]+dp[i][1][d][0]+\sum_{j=2}^d\sum_{k=0}^2dp[i][j][d][k]$. Here, $dp[i][1][d][1]$ is the number of ways to make a $d$-digit number equal to $B$, $dp[i][1][d][0]$ is the number of ways to make a $d$-digit number less than $B$, and $\sum_{k=0}^2dp[i][j][d][k]$ is the number of ways to make a $(d-j+1)$-digit number.
Danny Mittal's code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Milkshake {
public static final long MOD = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
long a = Long.parseLong(tokenizer.nextToken());
long b = Long.parseLong(tokenizer.nextToken());
char[] digits = in.readLine().replace(" ", "").toCharArray();
long[][] answersLeft = solve(("" + (a - 1L)).toCharArray(), digits);
long[][] answersRight = solve(("" + b).toCharArray(), digits);
StringBuilder out = new StringBuilder();
for (int q = Integer.parseInt(in.readLine()); q > 0; q--) {
tokenizer = new StringTokenizer(in.readLine());
int l = Integer.parseInt(tokenizer.nextToken()) - 1;
int r = Integer.parseInt(tokenizer.nextToken()) - 1;
long answer = answersRight[l][r] - answersLeft[l][r];
answer += MOD;
answer %= MOD;
out.append(answer).append('\n');
}
System.out.print(out);
}
static long[][] solve(char[] limit, char[] digits) {
long[][] answers = new long[digits.length][digits.length];
for (int j = 0; j < digits.length; j++) {
long[][][] dp = new long[limit.length][limit.length][3];
for (int k = j; k < digits.length; k++) {
for (int x = 0; x < limit.length; x++) {
for (int y = limit.length - 1; y > x; y--) {
if (digits[k] > limit[x]) {
for (int c = 0; c <= 2; c++) {
dp[x][y][2] += dp[x + 1][y][c];
}
} else if (digits[k] == limit[x]) {
for (int c = 0; c <= 2; c++) {
dp[x][y][c] += dp[x + 1][y][c];
}
} else {
for (int c = 0; c <= 2; c++) {
dp[x][y][0] += dp[x + 1][y][c];
}
}
dp[x][y][2] += dp[x][y - 1][2];
dp[x][y][compare(digits[k], limit[y])] += dp[x][y - 1][1];
dp[x][y][0] += dp[x][y - 1][0];
for (int c = 0; c <= 2; c++) {
dp[x][y][c] %= MOD;
}
}
}
for (int x = 0; x < limit.length; x++) {
dp[x][x][compare(digits[k], limit[x])] += 2;
}
for (int x = 0; x < limit.length; x++) {
answers[j][k] += dp[x][limit.length - 1][0];
answers[j][k] += dp[x][limit.length - 1][1];
if (x != 0) {
answers[j][k] += dp[x][limit.length - 1][2];
}
answers[j][k] %= MOD;
}
}
}
return answers;
}
static int compare(char a, char b) {
return Integer.signum(a - b) + 1;
}
}