Codeforces Round #FF (Div. 1) |
---|
Закончено |
DZY владеет 2m островами рядом с домом, острова пронумерованы от 1 до 2m. DZY очень любит мосты, поэтому между некоторыми островами он построил мосты. Проход по одному такому мосту занимает у DZY один день.
DZY любит математику, поэтому все мосты он строил по следующему правилу. Для каждой пары островов u, v (u ≠ v) он построил 2k различных мостов, соединяющих эти острова, где (a|b значит, что b делится на a). Все эти мосты были двусторонние.
DZY также построил некоторые мосты для связи его дома с островами. В частности, с островом i его дом соединен ai различными мостами. Эти мосты односторонние, поэтому после того, как DZY пройдет по одному из них, дороги домой уже не будет.
DZY решил погулять по островам. В самом начале прогулки он находится дома. Затем DZY выбирает один из мостов, идущих от его дома. Так он добирается до некоторого острова. После этого он проводит на островах t дней. Каждый день он выбирает, остаться ли ему на текущем острове и отдохнуть, или же дойти по мосту до другого острова. На острове можно оставаться дольше, чем на день. Также разрешается пересекать любой мост более одного раза.
Предположим, что в момент времени сразу после t-го дня DZY находится на i-м острове. Обозначим за ans[i] количество способов дойти до i-го острова ровно за t дней прогулки по островам. Ваша задача — подсчитать ans[i] для каждого i по модулю 1051131.
Чтобы избежать громоздких входных данных, массив a генерируется следующим образом. Вам даны s первых элементов массива: a1, a2, ..., as. Все остальные элементы надо подсчитать по формуле: ai = (101·ai - s + 10007) mod 1051131 (s < i ≤ 2m).
В первой строке записаны три целых числа: m, t, s (1 ≤ m ≤ 25; 1 ≤ t ≤ 1018; 1 ≤ s ≤ min(2m, 105)).
Во второй строке записано s целых чисел: a1, a2, ..., as (1 ≤ ai ≤ 106).
Чтобы избежать громоздких выходных данных, выведите только xor-сумму всех ans[i] по модулю 1051131 (1 ≤ i ≤ 2m). Другими словами выведите (ans[1] mod 1051131) xor (ans[2] mod 1051131) xor... xor (ans[n] mod 1051131).
2 1 4
1 1 1 2
1
3 5 6
389094 705719 547193 653800 947499 17024
556970
В первом примере массив ans равен [6, 7, 6, 6].
В первом примере, если юноша хочет быть на острове 1 через, гуляя по островам 1 день, то у него есть 6 различных способов сделать это:
Во втором примере (a1, a2, a3, a4, a5, a6, a7, a8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849). Массив ans равен [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335].
Название |
---|