DDOSvoid's Blog

CF 1599F Mars

发表于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/problemset/problem/1599/F

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问给定 $[l,r]$ 和 $d$，问 $[l,r]$ 内的数在模 $1e9+7$ 意义下是否可以构成一个差为 $d$ 的等差数列

$n,m\le 2\times 10^5$

Solution

我们考虑如果不是在模意义下，那么我们可以使用最经典的 $hash$ 方法，随机一个底数 $g$，数 $x$ 的 $hash$ 值为 $g^x$，那么对于一个首项为 $a$，公差为 $d$，长度为 $n-1$ 的等差数列的 $hash$ 值为 $g^{\sum_{i=0}^{n-1}a+di}$，这个东西是一个等比数列可以直接套用等比数列求和公式，但可惜的是指数位置上不能直接取模，所以我们不能使用这个方法来 $hash$

我们考虑更换 $hash$ 方法为随机一个指数 $k$，数 $x$ 的 $hash$ 值为 $x^k$，那么等差数列的 $hash$ 值为 $\sum_{i=0}^{n-1}(a+di)^k=\sum_{i=0}^{n-1}\sum_{j=0}^{k}\binom{k}{j}a^j(di)^{k-j}=\sum_{j=0}^j\binom{k}{j}a^jd^{k-j}\sum_{i=0}^{n-1}i^k$，这个东西可以 $O(nk)$ 预处理，$O(k)$ 单次求

但是如果我们取的 $k$ 太小的话可能会被卡掉，所以我们需要多取几个，这里我取了 $k\in[1,10]$，时间复杂度为 $O((n+m)k)$，处理的好的话可以避免所有快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#define maxn 200010
#define maxm 11
#define ll long long
using namespace std;

const int p = 1000000007;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; }
int pow_mod(int x, int n) {
    int s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s; 
}
const int inv2 = pow_mod(2, p - 2); 

int n, m, a[maxn];
int s[maxn][maxm], pre[maxn];

int f[maxn][maxm], C[maxm][maxm];
void init(int n) {
    for (int i = 0; i <= n; ++i) {
        f[i][0] = 1;
        for (int j = 1; j <= 10; ++j) f[i][j] = mul(f[i][j - 1], i);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= 10; ++j) f[i][j] = add(f[i][j], f[i - 1][j]); 

    for (int i = 0; i <= 10; ++i) C[i][0] = 1;
    for (int i = 1; i <= 10; ++i)
        for (int j = 1; j <= i; ++j) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];

    for (int i = 1; i <= n; ++i) {
        s[i][0] = 1; 
        for (int j = 1; j <= 10; ++j) s[i][j] = mul(s[i][j - 1], a[i]);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= 10; ++j) s[i][j] = add(s[i][j], s[i - 1][j]); 
}

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

    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i], pre[i] = add(pre[i - 1], a[i]);
    init(n);
    while (m--) {
        int l, r, d, a, len; cin >> l >> r >> d;
        len = r - l + 1; bool ok = true;
        a = mul(add({ pre[r], p - pre[l - 1], p - mul({ d, len, len - 1, inv2 }) }), pow_mod(len, p - 2));
        for (int i = 1, invd = pow_mod(d, p - 2), Dk = d; i <= 10; ++i, Dk = mul(Dk, d)) {
            int res = 0, ak = 1, dk = Dk;
            for (int j = 0; j <= i; ++j) {
                res = add(res, mul({ C[i][j], ak, dk, f[len - 1][i - j] }));
                ak = mul(ak, a); dk = mul(dk, invd);
            }
            if (res != add(s[r][i], p - s[l - 1][i])) { ok = false; break; } 
        } cout << (ok ? "Yes" : "No") << "\n";
    }
    return 0; 
}