題目鏈接：

http://codeforces.com/contest/658/problem/D

題意：

給定合法多項式，改變一項的系數(shù)，使得P(2)=0，問有多少種方法？

分析：

暴力求和然后依次試一試肯定不行啦~
仔細想想，多項式和為0，就是說存在某個2i，使得剩下的和等于x?2i，（其中x 的絕對值小于等于k）。
那我們就從最小的開始看。把系數(shù)依次向后移。
如果系數(shù)ai為偶數(shù)，那么ai?2i=(ai/2)?2i+1，就令bi=0，否則bi=1，最終所有系數(shù)都移到了2n上。
如果某個bi為奇數(shù)的話，就是說不能完全轉(zhuǎn)化成后面的數(shù)，無法用比他大的數(shù)表示他，那么后面的系數(shù)怎么變也抵消不了。所以我們只能看他自己和他前面的元素，通過改變這些元素的系數(shù)試圖抵消它。
最后倒著算一遍，算出對于每個位置，可以抵消后面的數(shù)的系數(shù)，然后。。。減一下他自己。。。就可以了。。。。
然后注意一下倒著求和過程中res的絕對值大于INF的情況，直接break。

代碼：

#include <cstdio> const int maxn = 200005, INF = 1e18; long long t[maxn],a[maxn], b[maxn]; int main (void) {int n, k;long long res = 0;scanf("%d%d",&n, &k);for(int i = 0; i <= n; i++){scanf("%I64d",&a[i]);}b[n] = a[n];int flag;for(int i = 0; i < n; i++){int tmp = b[i] + a[i] ;b[i + 1] += tmp / 2ll;b[i] = tmp % 2ll;}for(int i = 0; i <= n; i++){if(b[i]){flag = i; break;}//記錄}int cnt = 0;for(int i = n; i >= 0; i--){res = res * 2ll + b[i];if(res > INF || res < -INF )break;if(i <= flag){int ans = a[i] - res;if(ans >= -k && ans <= k && (ans != 0 || i != n)){cnt++;}}}printf("%d\n", cnt); } /* 5 5 0 -4 -2 -2 0 5 */

---

智商壓制，想的有點久。。。不過還是漲姿勢！

轉(zhuǎn)載于:https://www.cnblogs.com/Tuesdayzz/p/5758691.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 658D Bear and Polynomials【数学】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。