题意:有一长度为\(n\)的\(01\)序列,每次可以将序列元素右移\(d\)个单位,然后原序列和新序列每个元素取&,问你最少操作多少次使得序列所有元素都为\(0\),或者不存在.

题解:对于大小为\(1\)的位置,它一定只能被某个是\(0\)的位置移动过来变成\(0\),所以我们考虑\(0\)的位置,移动后的新位置为\((i+d)%n\),如果新位置为\(0\),那么我们不操作,如果是\(1\),那么操作一次将其变为\(0\),之后再用新位置的\(0\)去覆盖其他位置的\(1\)(也可能不覆盖),用优先队列维护操作次数,直到没有\(1\)为止

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
 
 
int main() {
    int _;
    scanf("%d",&_);
    while(_--){
        int n,d;
        scanf("%d %d",&n,&d);
        vector<int> a(n+1);
        priority_queue<PII,vector<PII>,greater<PII>> h;
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
            if(!a[i]) h.push({0,i});
        }
        int ans=0;
        while(!h.empty()){
            auto now=h.top();
            h.pop();
            int cur=(now.se+d)%n;
            if(a[cur]==0) continue;
            a[cur]=0;
            h.push({now.fi+1,cur});
            ans=max(ans,now.fi+1);
        } 
        bool flag=true;
        for(int i=0;i<n;++i){
            if(a[i]){
                flag=false;
                break;
            }
        }
        if(flag){
            printf("%d\n",ans);
        }
        else puts("-1");
    }
 
 
 
    return 0;
}