B. Дзи FFT-д дуртай

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дзи "Fast Fourier Transformation"-д дуртай ба тэр үүнийг ашиглах дуртай.

"Fast Fourier Transformation" бол эргэлтийг тооцоолход ашигладаг алгоритм юмаа. Тухайлбал, хэрвээ $n$ урттай $a$, $b$ болон $c$ дарааллууд нь $0$-оос $n - 1$ хүртэл индекслэгдсэн ба

Бид $c$-ийг "Fast Fourier Transformation"-ийг ашиглаж хурдан тооцоолж чадна.

Дзи энэ томъёонд жаахан өөрчлөлт хийсэн. Одоо

Бүх зүйлийг хялбар болгохын тулд $a$-гийн бүхэл тоон сэлгэмэл $1$-ээс $n$ хүртэл, харин $b$ дараалал зөвхөн $0$ ба $1$-ийг агуулна. $a$ ба $b$ өгөгдөх ба Дзи-д $c$-г тооцоолоход туслах хэрэгтэй байна.

Тэр дэггүй учраас DZY $a$ болон $b$ авахад тусгай арга нь болдог. Таньд гурван бүхэл $n$, $d$, $x$ тоонууд хэрэгтэй. $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)]);  
    }  
}

Оролт

Нэг мөрөнд гурван зайгаар тусгаарлагдсан бүхэл $n, d, x (1 ≤ d ≤ n ≤ 100000; 0 ≤ x ≤ 1000000006)$ тоонуудыг оруулна. Дзи дүрсгүй учраас $x$ нь $27777500$-тэй тэнцүү байж болохгүй.

Гаралт

$n$ ширхэг мөр хэвлэнэ. Энэ нь $i$-р мөр дахь бүхэл $c_{i - 1}$ тоог хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 1 1
Гаралт
1
3
2
Оролт
5 4 2
Гаралт
2
2
4
5
5
Оролт
5 4 3
Гаралт
5
5
5
5
4

Тэмдэглэл

Эхний жишээнд $a$ нь $[1 3 2]$, $b$ нь $[1 0 0]$, иймээс $c_{0} = max(11) = 1$, $c_{1} = max(10, 31) = 3$, $c_{2} = max(10, 30, 21) = 2$ байна.

Хоёр дахь жишээнд $a$ нь $[2 1 4 5 3]$, $b$ is $[1 1 1 0 1]$.

Гурав дахь жишээнд $a$ нь $[5 2 1 4 3]$, $b$ is $[1 1 1 1 0]$.

Сэтгэгдлүүдийг ачааллаж байна...