← 返回题目列表

Codeforces · 676/E

E. 人类与人工智能的最后一战

中文机器翻译题面 查看原题

距离上一次围棋中人对计算机的胜利已经过去了 100 年。技术向前迈出了一大步,机器人征服了地球!现在是人类和机器人之间的最后一战的时候了,这将决定地球的信仰。

选择以下游戏进行战斗:最初有一个多项式

P(x) = anxn + an - 1xn - 1 + ... + a1x + a0,

如果存在表示 P(x) = B(x)Q(x),其中 B(x) 也是某个多项式,则称多项式 P(x) 可被多项式 Q(x) 整除。

有些动作已经做出了,现在你想知道,如果人类发挥最佳,真的可以保证胜利吗?

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 100 000, |k| ≤ 10 000) - 多项式的大小和整数 k。

以下 n + 1 行中的第 i 行包含字符“?”如果 xi - 1 附近的系数尚未定义,或者整数值 ai,如果系数已知 (- 10 000 ≤ ai ≤ 10 000)。每个整数 ai(甚至 an)都可以等于 0。

请注意,我们不能保证您能获得轮到计算机移动的游戏位置。

输出

如果人类有获胜策略,则打印“是”(不带引号),否则打印“否”(不带引号)。

示例

输入 #1

1 2
-1
?

输出 #1

Yes

输入 #2

2 100
-10000
0
1

输出 #2

Yes

输入 #3

4 5
?
1
?
1
?

输出 #3

No

注意

在第一个样本中,计算机在第一步中将 a0 设置为 - 1,因此如果人类可以将系数 a1 设置为 0.5 并获胜。

在第二个样本中,所有系数都已设置,并且生成的多项式可被 x - 100 整除,因此人类获胜。