[USACO16JAN] Subsequences Summing to Sevens S 解析

[USACO16JAN] Subsequences Summing to Sevens S

https://www.luogu.com.cn/problem/P3131
方法 1: 暴力枚举端点并求和时间复杂度 \(50000^3\) 会 TLE
方法 2: 暴力枚举端点并前缀和优化时间复杂度 \(50000^2\) 还是会 TLE
方法 3:
一个小定理: 如果 \(a\) 模 \(c\) 和 \(b\) 模 \(c\) 相等的话, 那么 \(a-c\) 模 \(b\) 为零.
用数学公式写就是: \(a \equiv b \pmod c\) 则 \((a - b) \equiv 0 \pmod c\)
很好证明: 若 \(a \bmod c = b \bmod c = x\) 的话, 我们可以将 \(a\) 视作若干个 \(c\) 加上一个 \(x\), \(b\) 同理, 二者相减, 多出来的这个 \(x\) 就被抵消了, 所以 \((a - b) \equiv 0 \pmod c\).
那这和题目有什么关系呢?
我们计算出给定数组 \(arr\) 的前缀和数组 \(sum\), 并对 \(sum\) 中每个数都模 \(7\) 得到一个新数组 \(remainder\).
如果对于一对 \(i, j\), \(i < j\) 满足 \(remainder_i = remainder_j\) 的话, 那就表示在 \(arr\) 的 \((i,j]\) 中加起来能被 \(7\) 整除.
为什么呢? 这两个数满足 \(sum_i \equiv sum_j \pmod 7\), 根据上面所说的定理, 那么它也满足 \((sum_j-sum_i) \equiv 0 \pmod c\), 对于一个前缀和数组 \(sum_j - sum_i\) 意味着什么就不用我多说了吧.
所以接下来, 我们只需要找到一对 \(i, j\), 使 \(remainder_i = remainder_j\) 且 \(j - i\) 最大即可.
具体方法就是定义一个 \(l, r\) 数组, \(l_i\) 表示在 \(remainder\) 中第一个出现的 \(i\), \(r_i\) 表示最后一个出现的 \(i\).
然后遍历 \(i = 0..6\) 依次计算其 \(r_i - l_i\), 找出最大值即可 (为什么只有 \(0..6\)? 因为模过 \(7\) 了)
CODE

[code]#include #include #include #include using namespace std;const int N = 5e4 + 10;int arr[N], sum[N];int l[10], r[10];int main() {    int n;    cin >> n;    for (int i = 1; i > arr;        // 因为我们之后不需要再用到前缀和数组了, 所以就让它当 remainder 吧, 节省一份空间.        sum = (sum[i - 1] + arr) % 7;    }        // 为什么是 n..0 而不是 n..1?        // 因为计算前缀和 1..n 是 sum[n] - sum[1 - 1].    for (int i = n; i >= 0; i --) l[sum] = i;        for (int i = 0; i