感觉这题被智力打击了。。
刚开始我想的是对于每个位置我们可以暴力找出最后的位置在哪里。
因为对于当前位置p， 在进行第x步操作时,
如果p % x == 1 则 p = p + x - 1
否则 p = p - 1
并且第一步只有nlogn次， 所以我们可以暴力找出p % x == 1的情况， 然后更新， 然后就被卡常惹。。
主要是存因子要2s钟， 卡常卡一辈子卡不过去。
其实我们发现每一步操作只有两种点， 一种p = p - 1, 另一种是 p = p + x - 1
那么我们将p = p - 1的不移动， 相当于整体往前移动一格， 改变哪些 p = p + x - 1的， 这样就可以了。。。。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std; const int N = 2e6 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1); int n, a[N]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) a[i] = i; int L = 1, R = n; for(int i = 2; i <= n; i++) { int p = n / i * i - 1 + L; a[R + 1] = a[p + 1]; while(p - i >= 0) { a[p + 1] = a[p - i + 1]; p -= i; } L++; R++; } for(int i = L; i <= R; i++) printf("%d ", a[i]); puts(""); return 0; } /* */
Codeforces 286B Shifting (看题解)
原文：https://www.cnblogs.com/CJLHY/p/10456391.html