CF639C Bear and Polynomials

小北极熊 Limak 没有很多玩具，因此他经常玩多项式。 他认为一个多项式是合法的，当且仅当它的次数为 $n$，且所有系数都是绝对值不超过 $k$ 的整数。更正式地说： 设 $a_0, a_1, ..., a_n$ 为多项式系数，则 $P(x) = a_0 + a_1 x + \cdots + a_n x^n$。当且仅当同时满足下列条件时，多项式 $P(x)$ 是合法的： - 对于每个 $i$，$a_i$ 是整数； - 对于每个 $i$，$|a_i| \leq k$； - $a_n \neq 0$。 最近 Limak 得到了一个合法的多项式 $P$，其系数为 $a_0, a_1, a_2, ..., a_n$。他发现 $P(2) \neq 0$，于是打算将它改变。他想通过修改一个系数，得到一个次数为 $n$ 的合法多项式 $Q$，并使得 $Q(2) = 0$。请你计算有多少种不同的方式可以实现。 如果得到的目标多项式中的系数不同，则视为不同的方式。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 200000, 1 \leq k \leq 10^{9}$），分别表示多项式的次数和系数绝对值的限制。 第二行包含 $n+1$ 个整数 $a_0, a_1, ..., a_n$（$|a_i| \leq k, a_n \neq 0$），描述一个合法的多项式 $P(x) = a_0 + a_1 x + \cdots + a_n x^n$。保证 $P(2) \neq 0$。

输出可以通过修改一个系数得到合法多项式且 $Q(2)=0$ 的方式数。

在第一个样例中，给定多项式 $P(x) = 10 - 9x - 3x^2 + 5x^3$。 Limak 可以通过三种方式修改一个系数： 1. 令 $a_0 = -10$，得到 $Q(x) = -10 - 9x - 3x^2 + 5x^3$，此时 $Q(2) = -10 - 18 - 12 + 40 = 0$。 2. 令 $a_2 = -8$，得到 $Q(x) = 10 - 9x - 8x^2 + 5x^3$，此时 $Q(2) = 10 - 18 - 32 + 40 = 0$。 3. 令 $a_1 = -19$，得到 $Q(x) = 10 - 19x - 3x^2 + 5x^3$，此时 $Q(2) = 10 - 38 - 12 + 40 = 0$。 在第二个样例中，给出的多项式相同，但 $k=12$。此时上述三种方式中，只有前两种的结果合法，第三种方式因为 $|a_1| > k$ 不合法。因此答案为 $2$。 由 ChatGPT 5 翻译