Прошло 100 лет с тех пор, как в последний раз человек обыграл компьютер в Го. Технологии шагнули далеко вперёд, и роботы захватили нашу планету! Настало время финальной интеллектуальной схватки людей и машин. Если человек проиграет — всем нам конец, если выиграет — роботы покинут нашу планету.
В качестве интеллектуального состязания было принято выбрать следующую игру: есть многочлен
Говорят, что многочлен P(x) без остатка делится на многочлен Q(x), если существует представление P(x) = B(x)Q(x), где B(x) также является многочленом от x.
Прошло несколько ходов от начала игры, и вас заинтересовало, правда ли, что в текущей позиции человек может гарантировать себе победу, как бы ни действовал компьютер.
В первой строке входных данных содержатся два целых числа n и k (1 ≤ n ≤ 100 000, |k| ≤ 10 000) — размер многочлена и число k.
В i-й из последующих n + 1 строк содержится либо символ «?», если значение коэффициента при xi - 1 ещё не определено, либо целое число ai, если коэффициент при xi - 1 уже известен (|ai| ≤ 10 000). Любое из чисел, в том числе an может быть равно 0.
Обратите внимание, не гарантируется, что вам дана позиция игры, в которой сейчас ходит компьютер.
Выведите «Yes» (без кавычек), если человечество сможет спастись, и «No» (без кавычек) в противном случае.
1 2
-1
?
Yes
2 100
-10000
0
1
Yes
4 5
?
1
?
1
?
No
В первом тестовом примере компьютер первым ходом присвоил a0 значение - 1, таким образом на следующем ходу человек может присвоить оставшемуся коэффициенту перед x значение 0.5 и победить.
Во втором тестовом примере все коэффициенты уже проставлены и получившийся многочлен делится на x - 100, поэтому человек выиграл.
| Codeforces Round 354 (Div. 2) |
|---|
| Закончено |
