What is the Codeforces Round #XXX problem set like?

本文共计1069个文字，预计阅读时间需要5分钟。

100年后，人类与计算机在围棋上的上次胜利已经过去。科技发展迅猛，人工智能逐渐崭露头角。

E. The Last Fight Between Human and AI

time limit per test 1 second

memory limit per test 256 megabytes

input standard input

output standard output

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) = anxn + an - 1xn - 1 + ... + a1x + a0, 

with yet undefined coefficients and the integerk. Players alternate their turns. At each turn, a player pick some indexj, such that coefficientajthat stay nearxjis not determined yet and sets it toanyvalue (integer or real, positive or negative,0is also allowed). Computer moves first. The human will be declared the winner if and only if the resulting polynomial will be divisible byQ(x) = x - k.

PolynomialP(x)is said to be divisible by polynomialQ(x)if there exists a representationP(x) = B(x)Q(x), whereB(x)

Some moves have been made already and now you wonder, is it true that human can guarantee the victory if he plays optimally?

Input

The first line of the input contains two integersnandk(1 ≤ n ≤ 100 000, |k| ≤ 10 000)— the size of the polynomial and the integerk.

Thei-th of the followingn + 1lines contain character '?' if the coefficient nearxi - 1is yet undefined or the integer valueai, if the coefficient is already known ( - 10 000 ≤ ai). Each of integersai(and evenan) may be equal to0.

Please note, that it's not guaranteed that you are given the position of the game where it's computer's turn to move.

Output

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

Examples

input

1 2
-1
?

output

Yes

input

2 100
-10000
0
1

output

Yes

input

4 5
?
1
?
1
?

output

No

Note

In the first sample, computer seta0to - 1on the first move, so if human can set coefficienta1to0.5

In the second sample, all coefficients are already set and the resulting polynomial is divisible byx - 100, so the human has won.

题解：

输入一个P(x)，没有系数，求可不可能P(x) = B(x)Q(x)，其中Q(x)=x-k，由机器人先开始，计算人类会不会赢，并且局面可能是玩了几局之后的局面。

(x-k)|P(x)等价于P(k)==0，分两种情况考虑，if（k=0），谁先使得a[0]=0就谁赢。如果k！=0的话，注意到每一步都可以任意改变P(k)的值，因此只有最后一步是有用的，如果所有数都已经确定，那么检查P(k)是否为0，否则胜负取决于最后一步操作的先手。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int poly[100010],idx=0;
int well(int n,int k){
long long ans=0;

for(int i=n;i>=0;i--){
ans=ans*(long long)k+(long long)poly[i];
if(ans>10000000000||ans<-10000000000) return 0;
}
if(ans==0) return 1;
return 0;
}
int main(){
int n,k,unknown=0;
char tmp[10];
int position;
scanf("%d%d",&n,&k);
for(int i=0;i<=n;i++){
scanf("%s",&tmp);
if(tmp[0]=='?'){
unknown++;
position=i;
if(i==0) idx=1;
}
poly[i]=atoi(tmp);

}
if(k==0){
if(idx){
if((n+1-unknown)%2==0) printf("No");
else printf("Yes");
}
else{
if(poly[0]==0) printf("Yes");
else printf("No");
}
}
else if(unknown>=1) {
if(n%2==0) printf("No");
else printf("Yes");
}

else{

if(k==1){
long long sum=0;
for(int i=0;i<=n;i++){
sum+=(long long)poly[i];
}
if(sum==0) printf("Yes");
else printf("No");
}
else if(k==0){
if(poly[0]==0) printf("Yes");
else printf("No");
}
else if(k==-1){
long long sum=0;
for(int i=0;i<=n;i++){
if(i%2==0) sum+=(long long)poly[i];
else sum-=(long long)poly[i];
}
if(sum==0) printf("Yes");
else printf("No");
}
else {
if(well(n,k)) printf("Yes");
else printf("No");
}
}
return 0;
}