Codeforces ラウンド #254 (ディビジョン 2)D(推定)_html/css_WEB-ITnose

D. DZY Loves FFT

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

DZYは速いのが大好きフーリエ変換、そして彼はそれを使うのを楽しんでいます。

高速フーリエ変換は、畳み込みを計算するために使用されるアルゴリズムです。具体的には、a、b、c が長さ n のシーケンスで、0 から n?-?1 までインデックスが付けられている場合、

高速フーリエ変換を使用して c を高速に計算できます。

DZY はこの式に少し変更を加えました。さて

話を簡単にするために、a は 1 から n までの整数の順列で、b は 0 と 1 のみを含むシーケンスです。a と b が与えられた場合、DZY は c を計算するためにあなたの助けが必要です。

彼はいたずらなので、 DZY は、a と b を取得する特別な方法を提供します。必要なのは、n、d、x の 3 つの整数だけです。それらを取得したら、以下のコードを使用して a と 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)]);    }}

演算 x % y は、x を y で割った後の剰余を示します。関数 swap(x, y) は、2 つの値 x と y を交換します。

入力

入力の唯一の行には、スペースで区切られた 3 つの整数 n,?d,?x (1?≤?d?≤?n?) が含まれています。 ≤?100000; 0?≤?x?≤?1000000006）。 DZY は不正なため、x は 27777500 に等しくありません。

出力

n 行の出力、i 番目の行には整数 ci?-?1 が含まれている必要があります。

サンプル テスト

入力

3 1 1

出力

132

入力

5 4 2

出力

22455

入力

5 4 3

出力

55554

题意：RT

思路：故に b 配列一定只含 0 または 1、那么含 0 的是不意図的

直接好了、その後用一数组は[]记录前どのくらいのb配列が1の位置

每次要找最大值的時候、如果is[]数组的数组一常数未満、就枚is数组

いいえ则直接从大到小枚举最大值就好了