【Codeforces 639C】Bear and Polynomials

  如果能通过修改\(a_i\)来使\(Q(2)=0\)，那么i满足两个条件：

    1.\[\sum_{j=0}^{i-1}{2^j a_j} \equiv \  0 \  (mod\  2^i)\]

    2.\[|\frac{\sum_{j=i+1}^n{a_j2^j}}{2^i}+\lfloor\frac{\sum_{j=0}^{i-1}{a_j2^j}}{2^i}\rfloor|<=k\]

  然后做好预处理工作就可以写了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200010;

int t[maxn];
int a[maxn];
int n,k,val;
long long cnt;
int ans;

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=0;i<=n;i++) scanf("%d",&a[i]);
	val=-1;
	for (int i=0;i<=n;i++)
	{
		if (t[i]&1) {val=i-1;break;}
		t[i]>>=1;
		if (i==n) {val=n;break;}
		t[i+1]=a[i]+t[i];
	}
	for (int i=n;i>=0;i--)
	{
		if (i<=val && abs(cnt+t[i])<=k) ans++;
		cnt=(cnt+a[i])<<1;
		if (abs(cnt)>k*2) break;
	}
	if (val==n && t[n]==0) ans--;
	printf("%d\n",ans);
	return 0;
}