(Analysis by Benjamin Qi, Jesse Choe)

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.

• Adding $a_i$ to the top of the pile is equivalent to adding $a_i \cdot 10^{s}$ to $k$. This corresponds to the DP transition $dp[i][a_i \cdot 10^s+k] \mathrel{+}= dp[i-1][k]$.
• Adding $a_i$ to the bottom of the pile is equivalent to changing $k$ to $10\cdot k + a_i$, corresponding to $dp[i][10 \cdot k + a_i]\mathrel{+}= dp[i-1][k]$.
• Not adding $a_i$ to the pile corresponds to $dp[i][k] \mathrel{+}= dp[i-1][k]$.

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];
}
int addLeft = pow(10, countDigits(k)) * d[j] + k;
}
}
}
}
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.util.StringTokenizer;

public class Milkshake {
public static final long MOD = 1000000007;

public static void main(String[] args) throws IOException {
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--) {
int l = Integer.parseInt(tokenizer.nextToken()) - 1;
int r = Integer.parseInt(tokenizer.nextToken()) - 1;
}
System.out.print(out);
}

static long[][] solve(char[] limit, char[] digits) {
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++) {
if (x != 0) {