CF1579F Array Stabilization (AND version)

Queryme · 2026-04-25 00:57:59 · 题解

好咕。

循环右移的数组肯定不陌生，这一题定死了循环的步宽 d。考虑按位与的性质，只要两个数中一个存在 0 则结果为 0。

那我们知道了每次操作的结果影响，就考虑序列循环右移影响到的范围。整个序列长为 n，步长为 d，令 g=(n,d)，这样将整个序列分成 g 块染色，g 种颜色按序染色，则我们保证同色块下标 i,j 满足 i \equiv j \pmod g。一个下标能够影响的永远只有其同色的部分下标。

现在得出思路，只要有一个位置为 0，则其能影响的所有下标都将会在几次位移后被按位与“传染”为 0。开一个临时 cnt 对全局答案 dp 即可。一个 1 只考虑离他最近的 0 需要跳几个 d 来影响他。

感觉表达的还是有点糟糕，哎看不懂的我只能说声抱歉，第一次写数论题解实在不知道怎么表达清楚。

代码复杂度 O(tn)。

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

const int N = 1e6 + 10;
int a[N];
bool vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while (t --) {
        int n, d;
        cin >> n >> d;
        fill(vis+1, vis+n+1, 0);
        for (int i=1;i<=n;i++)
            cin >> a[i];
        int ans=0;
        for (int i=1;i<=n;i++) {
            if (!a[i] && !vis[i]) {
                int cnt=0, st=i;
                while (!vis[st]) {
                    vis[st] = 1;
                    if (a[st]) ans = max(ans, cnt);
                    else cnt = 0;
                    st = (st-d+n-1) % n + 1;
                    ++cnt;
                }
            }
        }
        bool fg = 0;
        for (int i=1;i<=n;i++)
            if (!vis[i]) {
                fg = 1;
                break;
            }
        if (fg) cout << "-1\n";
        else cout << ans << '\n';
    }
    return 0;
}