The Last Fight Between Human and AI

题意翻译

机器人在和人类进行对决，现在给你一个多项式的中间状态，此时有些系数可能是确定的，有些系数可能是不确定的（用？表示），机器人和人将轮流为未知数设值（由于是中间状态所以当前第一个设值的人不一定是机器人），求人类在不管机器人如何设值的情况下，是否能让最终的f(k) = 0。 多项式表示为：输入整数n和k，下面的n + 1行中每行为一个整数或?，?表示未确定，这些整数表示的是一个多项式的系数，且从第二行开始起第i行表示的是x ^ (i - 1)的系数

题目描述

100 years have passed since the last victory of the man versus computer in Go. Technologies made a huge step forward and robots conquered the Earth! It's time for the final fight between human and robot that will decide the faith of the planet. The following game was chosen for the fights: initially there is a polynomial $ P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0}, $ with yet undefined coefficients and the integer $ k $ . Players alternate their turns. At each turn, a player pick some index $ j $ , such that coefficient $ a_{j} $ that stay near $ x^{j} $ is not determined yet and sets it to any value (integer or real, positive or negative, $ 0 $ is also allowed). Computer moves first. The human will be declared the winner if and only if the resulting polynomial will be divisible by $ Q(x)=x-k $ .Polynomial $ P(x) $ is said to be divisible by polynomial $ Q(x) $ if there exists a representation $ P(x)=B(x)Q(x) $ , where $ B(x) $ is also some polynomial. Some moves have been made already and now you wonder, is it true that human can guarantee the victory if he plays optimally?

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ k $ ( $ 1<=n<=100000,|k|<=10000 $ ) — the size of the polynomial and the integer $ k $ . The $ i $ -th of the following $ n+1 $ lines contain character '?' if the coefficient near $ x^{i-1} $ is yet undefined or the integer value $ a_{i} $ , if the coefficient is already known ( $ -10000<=a_{i}<=10000 $ ). Each of integers $ a_{i} $ (and even $ a_{n} $ ) may be equal to $ 0 $ . Please note, that it's not guaranteed that you are given the position of the game where it's computer's turn to move.

输出格式

Print "Yes" (without quotes) if the human has winning strategy, or "No" (without quotes) otherwise.

输入输出样例

输入样例 #1

1 2
-1
?

输出样例 #1

Yes

输入样例 #2

2 100
-10000
0
1

输出样例 #2

Yes

输入样例 #3

4 5
?
1
?
1
?

输出样例 #3

No

说明

In the first sample, computer set $ a_{0} $ to $ -1 $ on the first move, so if human can set coefficient $ a_{1} $ to $ 0.5 $ and win. In the second sample, all coefficients are already set and the resulting polynomial is divisible by $ x-100 $ , so the human has won.