Codeforces 1894C

Codeforces 1894C"/>

Codeforces 1894C

题目链接：

题意：

给定序列 a a a 有没有一个序列 b b b 能够根据固定点 a i = i a_i = i ai​=i 循环左移 i i i 次，问能否在 k k k 次之内序列 b b b 能够还原成序列 a a a 。

思路：

可以观察循环左移 i i i 次，那么移动后的 a i a_i ai​ 都变成 b n b_n bn​ ，因此可以逆向模拟 a l a s t a_{last} alast​ 能否回到第 n − i + 1 n-i+1 n−i+1 个操作后的序列 b b b 。可以发现当 a l a s t > n a_{last}>n alast​>n 是不满足题意输出 N o No No ，因为 a a l a s t = a l a s t = l a s t > n a_{a_{last}}=a_{last}=last>n aalast​​=alast​=last>n 。如果 k > n k>n k>n 那么可以发现每 n n n 次都是一次循环，所以只需 k = m i n ( k , n ) k=min(k,n) k=min(k,n)

代码：

#include <bits/stdc++.h>
#define endy {cout<<"Yes\n";}//return ;}❤
#define endn {cout<<"No\n";}//return ;}❤
#define endl '\n'
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<ll,ll> pii;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF_ = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
ll n, m, k, x, y, res = 0, sum = 0, ans = 0, ma = 0, mi = INF;
void solve()
{cin >> n >> k;vector<ll> a(n+1);for(int i = 1; i <= n; i ++) cin >> a[i];k = min(n, k);int last = n;while(k --) {if(a[last] > n){endn return;}last += (n - a[last]);last %= n;}endy
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);// cout.tie(0);ll _;cin>>_;while(_--)solve();return 0;
}