Official Editorial

Explanation

A little thing to notice that helps us in the right direction is that a possible test case can have queries that ask for one specific number, like

100 100

This motivates a prefix sum approach, where we calculate the answer for each possible integer and answer queries with a prefix sum array.

To actually count the number of non-palindromic arrays that sum to an integer (which we'll refer to as $x$ from now on), we can use complimentary counting.

To count the total number of arrays that sum to $x$, period, we evaluate the following summation:

In this summation, we sum over all possible lengths $l$ of the array, and then use stars and bars to count how many arrays of length $l$ sum to $x$. The initial subtraction of $l$ is to account for that all elements must be positive.

This expression then simplifies to

The binomial theorem is applied to simplify the summation.

It remains to count the number of palindromic arrays that sum to $x$. For this, there's two cases to consider: $x$ being even and $x$ being odd.

If $x$ is even, then it's possible to have an even-length palindromic array. Each half must sum to $\frac{x}{2}$ and since the two are basically identical, there's $2^{\frac{x}{2}-1}$ possible palindromic arrays of this form. However, we can also form an odd-length array by taking some even number from $x$ initially and setting it as the center element. This gives us a grand total of

The $1$ at the front is another edge case when we put all of $x$ as the middle. But anyways, notice that this actually simplifies to $2^{\frac{x}{2}}$! Pretty cool, huh?

If $x$ is odd, though, we can't have an even-length palindromic array. We can only take an odd amount from $x$ and set it as the center, giving us

This also simplifies like the one we did previously, only this time it's to $2^{\frac{x-1}{2}}$.

Implementation

Time Complexity: $\mathcal{O}(Q+N)$, where $N$ is the maximum value of $r$.

Copy
MOD = 10**9 + 7
MAX_VAL = 10**5

two_pows = [1]
for _ in range(1, MAX_VAL + 1):
	two_pows.append((two_pows[-1] * 2) % MOD)

pref_sums = [0]
for i in range(1, MAX_VAL + 1):
	if i % 2 == 0:

Copy
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_SUM = 1e5;
int mod(long long a) { return (a + MOD) % MOD; }

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