CF444B.DZY Loves FFT

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

DZY loves Fast Fourier Transformation, and he enjoys using it.

Fast Fourier Transformation is an algorithm used to calculate convolution. Specifically, if $a$ , $b$ and $c$ are sequences with length $n$ , which are indexed from $0$ to $n-1$ , and

We can calculate $c$ fast using Fast Fourier Transformation.

DZY made a little change on this formula. Now

To make things easier, $a$ is a permutation of integers from $1$ to $n$ , and $b$ is a sequence only containing $0$ and $1$ . Given $a$ and $b$ , DZY needs your help to calculate $c$ .

Because he is naughty, DZY provides a special way to get $a$ and $b$ . What you need is only three integers $n$ , $d$ , $x$ . After getting them, use the code below to generate $a$ and $b$ .

//x is 64-bit variable;
function getNextX() {
    x = (x * 37 + 10007) % 1000000007;
    return x;
}
function initAB() {
    for(i = 0; i < n; i = i + 1){
        a[i] = i + 1;
    }
    for(i = 0; i < n; i = i + 1){
        swap(a[i], a[getNextX() % (i + 1)]);
    }
    for(i = 0; i < n; i = i + 1){
        if (i < d)
            b[i] = 1;
        else
            b[i] = 0;
    }
    for(i = 0; i < n; i = i + 1){
        swap(b[i], b[getNextX() % (i + 1)]);
    }
}

Operation x % y denotes remainder after division $x$ by $y$ . Function swap(x, y) swaps two values $x$ and $y$ .

输入格式

The only line of input contains three space-separated integers $n,d,x (1<=d<=n<=100000; 0<=x<=1000000006)$ . Because DZY is naughty, $x$ can't be equal to $27777500$ .

输出格式

Output $n$ lines, the $i$ -th line should contain an integer $c_{i-1}$ .

输入输出样例

输入#1
```
3 1 1
```
输出#1
```
1
3
2
```
输入#2
```
5 4 2
```
输出#2
```
2
2
4
5
5
```
输入#3
```
5 4 3
```
输出#3
```
5
5
5
5
4
```

说明/提示

In the first sample, $a$ is $[1\ 3\ 2]$ , $b$ is $[1\ 0\ 0]$ , so $c_{0}=max(1·1)=1$ , $c_{1}=max(1·0,3·1)=3$ , $c_{2}=max(1·0,3·0,2·1)=2$ .

In the second sample, $a$ is $[2\ 1\ 4\ 5\ 3]$ , $b$ is $[1\ 1\ 1\ 0\ 1]$ .

In the third sample, $a$ is $[5\ 2\ 1\ 4\ 3]$ , $b$ is $[1\ 1\ 1\ 1\ 0]$ .

首页