TIOJ 1927：同步(Sync)

TIOJ 1927：同步(Sync)

題目大意：給你一個數列 $c_1\sim c_n$，每次會給你兩個位置 $i,j$，如果 $(c_ic_j)^{\frac{p - 1}{2}} = 1$，那就可以同步一次，並把 $i+1, j+1$，直到不同步或是 $i,j$ 其中一個超過 $n$。

解法：可以發現對於 $1≤x<p,\ x^{\frac{p - 1}{2}} = 1\ \text{or}\ p - 1$，那就可以將 $c$ 變成 $1$ 或 $p-1$，然後 $p-1$ 改成 $2$，對 $c\ \text{hash}$，每次詢問時就可以二分搜找出答案。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;
const int MOD = 1e9 + 7;
const int base = 137;

int n, q, a[SIZE];
int pro[SIZE], inv[SIZE], pre[SIZE];

int power (int d, int up) {
    int ans = 1;
    for (; up; d = 1ll * d * d % MOD, up >>= 1) if (up & 1) ans = 1ll * ans * d % MOD;
    return ans;
}

int cal (int p, int len) {
    int x = 1ll * (pre[p + len - 1] - pre[p - 1]) * inv[p] % MOD;
    return x < 0 ? x + MOD : x;
}

void solve() {
    cin >> n >> q;
    pro[0] = inv[0] = 1;
    pro[1] = base, inv[1] = power (base, MOD - 2);
    FOR (i, 2, n) {
        pro[i] = 1ll * base * pro[i - 1] % MOD;
        inv[i] = 1ll * inv[i - 1] * inv[1] % MOD;
    }
    FOR (i, 1, n) {
        cin >> a[i];
        a[i] = power (a[i], MOD / 2);
        a[i] = a[i] == MOD - 1 ? 2 : 1;
        pre[i] = (pre[i - 1] + 1ll * pro[i] * a[i]) % MOD;
    }
    while (q--) {
        int a, b;
        cin >> a >> b;
        a++, b++;
        int l = 0, r = min (n - a + 1, n - b + 1);
        while (l < r) {
            int mid = (l + r) / 2 + 1;
            if (cal (a, mid) == cal (b, mid)) l = mid;
            else r = mid - 1;
        }
        cout << l << '\n';
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！