CF 286B(Shifting-deque)

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 ≤ 的整数
 把 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;
}