CF1893A

EternityLove · 2023-11-22 08:58:57 · 题解

正着想操作不是很好想，考虑倒着想操作。

当你考虑操作的逆操作时，你会发现，相当于每次回退 a_n 格，这可以简单证明：你每次正着操作选择 a_x=x 的值，然后循环左移 x 位，那么原来 a_x 的值一定落在新的序列的 a_n 的位置。

那么你的问题转变为，b 序列能不能进行 k 次逆操作。

考虑什么时候不能进行逆操作，即当且仅当 a_n\gt n 时，序列不可进行逆操作。

此时可以考虑模拟整个过程，值得注意的是，我们每次操作不需要去移动数组，而只需要修改最后一个数的指针位置即可，比如当且最后一个数的指针在 now 的位置，那么模拟一次操作相当于只需要将这个指针循环左移 a_{now} 位即可。

由于 k 很大，我们完全模拟会超时，考虑优化。容易发现，如果当前指针已经被访问过了，说明已经进行了一个循环了，那么此时肯定有解，所以我们至多只需要模拟 n 次即可得到答案。

#include <bits/stdc++.h>
#define N 500010
#define ll long long
#define endl '\n'
using namespace std;

inline ll read() {
    char ch=getchar();ll ans=0,f=1;
    for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
    for (;isdigit(ch);ch=getchar()) ans=(ans<<3)+(ans<<1)+ch-'0';
    return ans*f;
}

int a[N],flag[N];

void slv() {
    int n,k;
    cin>>n>>k;
    for (int i = 0;i < n;++ i) cin>>a[i],flag[i]=0;
    int now=n-1;
    while (k && !flag[now]) {
        flag[now]=1;
        if (a[now]>n) {
            cout<<"No"<<endl;
            return;
        }
        now=(now-a[now]+n)%n;
        --k;
    }
    cout<<"Yes"<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    while (T--) {
        slv();
    }
    return 0;
}