B. Shifting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
John Doe has found the beautiful permutation formula.
Let's take permutation p = p1, p2, ..., pn.
Let's define transformation f of this permutation:
k (k > 1) 是每段长度, r 是最大满足 rk ≤ n 的整数
把 r
段和尾剩余部分(如果有)左移.
求序列 f(f( ... f(p = [1, 2, ..., n], 2) ... , n - 1), n) .
Input
一行 n (2 ≤ n ≤ 106).
Output
Print n distinct space-separated integers from 1 to n —
a beautiful permutation of size n.
Sample test(s)
input
2
output
2 1
input
3
output
1 3 2
input
4
output
4 2 3 1
Note
A note to the third test sample:
- f([1, 2, 3, 4], 2) = [2, 1, 4, 3]
- f([2, 1, 4, 3], 3) = [1, 4, 2, 3]
- f([1, 4, 2, 3], 4) = [4, 2, 3, 1]
这题我是用WJMZBMR的神模拟过的。
先普及一下deque< >
deque<int> deq; //建立双端队列
deq.push_back(x)
deq.push_front(x)
deq.pop_back(x)
deq.pop_back(x)
然后可以模拟了,每次把每段的最后搬上来。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<queue> using namespace std; #define MAXN (1000000+10) deque<int> deq; int n; int main() { cin>>n; for (int i=1;i<=n;i++) deq.push_back(i); for (int i=2;i<=n;i++) { int l=(n-1)/i*i;deq.push_back(deq[l]); while (l-i>=0) { deq[l]=deq[l-i]; l-=i; } deq.pop_front(); } for (int i=0;i<deq.size();i++) cout<<deq[i]<<' '; return 0; }