CodeforcesRound.770.Div2-F Fibonacci Additions

题目链接

Contest #770 - Problem F

题目描述

You are given two arrays \(A\) and \(B\) of the same length. We will ask you to perform several Fibonacci additions on these arrays with different parameters, and after each operation you have to report whether arrays \(A\) and \(B\) are equal modulo \(MOD\) .

注意事项

• 中间变量会超出INT_MAX
• (bool) a[i] 的使用

AC代码

#include <iostream>

using namespace std;

const int MAXN = 3e5 + 5;
int n, q, MOD, a[MAXN], f[MAXN], cnt;

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

    cin >> n >> q >> MOD;
    f[1] = 1;
    for (int i = 2; i <= n; i++)
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        int b;
        cin >> b;
        a[i] = (a[i] - b + MOD) % MOD;
    }
    for (int i = n; i >= 2; i--)
    {
        a[i] = ((long long) a[i] - a[i - 1] - a[i - 2] + MOD * 2) % MOD; // 规避溢出和Narrowing报错
        cnt += (bool) a[i];
    }
    cnt += (bool) a[1];
    while (q--)
    {
        char flag;
        int l, r;
        cin >> flag >> l >> r;
        cnt -= (bool) a[l];
        if (r + 1 <= n)
            cnt -= (bool) a[r + 1];
        if (r + 2 <= n)
            cnt -= (bool) a[r + 2];
        a[l] = (a[l] + (flag == 'A' ? 1 : MOD - 1)) % MOD;
        if (r + 1 <= n)
            a[r + 1] = (a[r + 1] + (flag == 'A' ? MOD - f[r - l + 2] : f[r - l + 2])) % MOD;
        if (r + 2 <= n)
            a[r + 2] = (a[r + 2] + (flag == 'A' ? MOD - f[r - l + 1] : f[r - l + 1])) % MOD;
        cnt += (bool) a[l];
        if (r + 1 <= n)
            cnt += (bool) a[r + 1];
        if (r + 2 <= n)
            cnt += (bool) a[r + 2];
        cout << (!cnt ? "YES" : "NO") << endl;
    }
    return 0;
}