Codeforces Round 254 (Div. 1) |
---|
Закончено |
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. Используйте приведенный ниже код, чтобы сгенерировать a и b.
//x - это 64-битная переменная
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) меняет местами два значения, x и y.
В единственной строке записаны три целых числа через пробел n, d, x (1 ≤ d ≤ n ≤ 100000; 0 ≤ x ≤ 1000000006). Как уже было сказано, DZY крайне капризный, поэтому x не может равняться 27777500.
Выведите n строк, в i-й строке выведите значение ci - 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], таким образом, c0 = max(1·1) = 1, c1 = max(1·0, 3·1) = 3, c2 = max(1·0, 3·0, 2·1) = 2.
Во втором примере a равняется [2 1 4 5 3], b равняется [1 1 1 0 1].
В третьем примере a равняется [5 2 1 4 3], b равняется [1 1 1 1 0].
Название |
---|