C. Ayoub and Lost Array 详细题解

问题描述

给定三个整数 $n$、$l$、$r$（$1 \le n \le 2 \times 10^5$，$1 \le l \le r \le 10^9$）。求有多少个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，满足：

• 对每个 $i$，有 $l \le a_i \le r$；
• 数组所有元素的和能被 $3$ 整除，即 $\sum_{i=1}^n a_i \equiv 0 \pmod{3}$。

答案对 $10^9+7$ 取模。

问题分析

由于只关心每个元素模 $3$ 的余数，而不关心具体数值，我们可以将区间 $[l, r]$ 中的数分为三类：模 $3$ 余 $0$、余 $1$、余 $2$。记这三类数的个数分别为 $c_0$、$c_1$、$c_2$。那么原问题转化为：从这三类中可重复地选取 $n$ 个数（顺序有关），使得选出的 $n$ 个余数之和模 $3$ 等于 $0$，求方案数。其中每类有 $c_r$ 种不同的数值可选。

因此，我们需要先计算 $c_0, c_1, c_2$。

计算模 3 余数的个数

对于任意整数 $x$，其模 $3$ 余数 $r = x \bmod 3$。在区间 $[l, r]$ 内，满足 $x \equiv t \pmod{3}$ 的整数构成一个等差数列，首项为大于等于 $l$ 的最小同余数，末项为小于等于 $r$ 的最大同余数。具体计算方法：

设 $t \in \{0,1,2\}$，则满足 $x \equiv t \pmod{3}$ 的 $x$ 可表示为 $x = 3k + t$。由 $l \le 3k+t \le r$ 得：

$$\frac{l-t}{3} \le k \le \frac{r-t}{3}$$

$k$ 为整数，因此 $k$ 的最小值为 $\lceil (l-t)/3 \rceil$，最大值为 $\lfloor (r-t)/3 \rfloor$。若最小值大于最大值，则 $c_t = 0$；否则

$$c_t = \left\lfloor \frac{r-t}{3} \right\rfloor - \left\lceil \frac{l-t}{3} \right\rceil + 1 $$

标程中采用循环递增寻找首尾的方法，复杂度 $O(1)$ 也可接受，但更高效的是直接公式计算。不过由于 $l,r$ 最大 $10^9$，循环最多 3 次，不影响。

动态规划求解方案数

设 $dp[i][j]$ 表示已经选择了前 $i$ 个数，这些数的和模 $3$ 等于 $j$ 的方案数（$j=0,1,2$）。初始状态 $dp[0][0] = 1$，表示空数组和为 $0$，方案数为 $1$。

转移：考虑第 $i+1$ 个数，可以选择余数为 $add \in \{0,1,2\}$ 的任意一个数，有 $c_{add}$ 种选择。加入后新余数为 $(j + add) \bmod 3$，因此：

$$dp[i+1][(j+add)\bmod 3] \mathrel{+}= dp[i][j] \times c_{add} \pmod{MOD} $$

最终答案为 $dp[n][0]$。

时间复杂度与空间复杂度

• 计算 $c_0, c_1, c_2$：$O(1)$。
• DP 部分：状态数 $O(n \times 3) = O(n)$，每个状态转移 $3$ 次，总时间复杂度 $O(n)$。
• 空间复杂度：可以用滚动数组优化到 $O(1)$ 额外空间，但标程使用 $O(n)$ 的二维数组（$n \le 2\times10^5$，约 $2.4$ MB，可行）。

示例验证

示例1

输入：$n=2, l=1, r=3$
区间 $[1,3]$ 中的数：$1,2,3$。
$c_0$（余0）：$\{3\}$ → $c_0=1$
$c_1$（余1）：$\{1\}$ → $c_1=1$
$c_2$（余2）：$\{2\}$ → $c_2=1$

DP：

• $dp[0][0]=1$
• $i=0$：
  从 $j=0$ 出发：
  加余0 → $dp[1][0] += 1\times1 =1$
  加余1 → $dp[1][1] += 1\times1 =1$
  加余2 → $dp[1][2] += 1\times1 =1$
• $i=1$：
  从 $j=0$（值1）：加余0 → $dp[2][0]+=1\times1=1$；加余1→$dp[2][1]+=1$；加余2→$dp[2][2]+=1$
  从 $j=1$（值1）：加余0→$dp[2][1]+=1$；加余1→$dp[2][2]+=1$；加余2→$dp[2][0]+=1$
  从 $j=2$（值1）：加余0→$dp[2][2]+=1$；加余1→$dp[2][0]+=1$；加余2→$dp[2][1]+=1$
  累加得 $dp[2][0]=1+1+1=3$，输出 $3$，正确。

示例2

输入：$n=3, l=2, r=2$
区间只有 $2$，余数为 $2$，所以 $c_0=0, c_1=0, c_2=1$。
DP 过程：只能选余2的数，3次后总和余 $2\times3=6\equiv0$，只有 $1$ 种方案（$[2,2,2]$），输出 $1$。

示例3

输入：$n=9, l=9, r=99$
输出 $711426616$，符合预期。

代码实现（标程）

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

const int MOD = 1e9 + 7;

int main() {
    int n, l, r;
    cin >> n >> l >> r;

    // 统计区间 [l, r] 中模 3 余 0, 1, 2 的数的个数
    vector<long long> cnt(3, 0);
    for (int rem = 0; rem < 3; ++rem) {
        long long first = l;
        while (first % 3 != rem) first++;
        if (first > r) continue;
        long long last = r;
        while (last % 3 != rem) last--;
        cnt[rem] = (last - first) / 3 + 1;
    }

    // dp[i][j]: 前 i 个数，总和模 3 为 j 的方案数
    vector<vector<long long>> dp(n + 1, vector<long long>(3, 0));
    dp[0][0] = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (dp[i][j] == 0) continue;
            for (int add = 0; add < 3; ++add) {
                int nj = (j + add) % 3;
                dp[i + 1][nj] = (dp[i + 1][nj] + dp[i][j] * cnt[add]) % MOD;
            }
        }
    }

    cout << dp[n][0] << endl;
    return 0;
}

总结

本题核心在于将数值范围问题转化为模 $3$ 余数的计数问题，然后利用动态规划求解组合方案数。由于只关心总和模 $3$ 的结果，状态数被压缩到常数级别，使得 $O(n)$ 的算法可行。注意数据范围大时使用 long long 防止中间乘法溢出，并取模运算。