CFR 639 C. Bear and Polynomials ( Hash )
題意:
給你 N 次多項式 F()。
係數的絕對值不能超過 K。
問你修改一個值之後,F( 2 ) = 0 的方案數。
特別的,A[ N ] != 0。
制約:
1 ≤ N ≤ 2e5
abs( K ) ≤ 1e9
解法:
哈希水掉。
原本不能暴力算的原因只是因為數字會太大,不過哈希就沒事了。
枚舉要改的係數下標,把它的貢獻移除掉之後,用模逆元計算新的係數應該是多少,才能在哈希的模下得到 0,最後再判這個新的係數是不是可行的就可以了。
實作上會用兩組模防止碰撞。
正負號的處理會有點讓人頭痛,詳見代碼。
複雜度:
O( N lg K )
#include <bits/stdc++.h> using namespace std; const int MOD[] = { int( 1e9 + 7 ), int( 1e9 + 9 ) }; const int MAXN = int( 2e5 + 1 ); int N, K; int A[ MAXN ]; int pb[ 2 ][ MAXN + 1 ]; int ph[ 2 ][ MAXN + 1 ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> K; ++N; for( int i = 0; i < N; ++i ) { cin >> A[ i ]; } reverse( A, A + N ); for( int t = 0; t < 2; ++t ) { pb[ t ][ 0 ] = 1; for( int i = 0; i < N; ++i ) { pb[ t ][ i + 1 ] = 2LL * pb[ t ][ i ] % MOD[ t ]; ph[ t ][ i + 1 ] = ( 2LL * ph[ t ][ i ] + A[ i ] ) % MOD[ t ]; } } if( ph[ 0 ][ N ] == 0 and ph[ 1 ][ N ] == 0 ) { cout << 0 << endl; exit( 0 ); } int ans = 0; for( int i = 0; i < N; ++i ) { int nv[ 2 ]; for( int t = 0; t < 2; ++t ) { int g = ( 1LL * ph[ t ][ N ] - 1LL * A[ i ] * pb[ t ][ N - 1 - i ] ) % MOD[ t ]; g *= -1; if( g < 0 ) g += MOD[ t ]; // let's find v for v * 2**(N-1-i) == g static auto fast_pow = [ & ]( int v, int p, int m ) { int res = 1; while( p ) { if( p & 1 ) { res = 1LL * res * v % m; } p >>= 1; v = 1LL * v * v % m; } return res; }; static auto inv_mod = [ & ]( int v, int m ) { return fast_pow( v, m - 2, m ); }; nv[ t ] = 1LL * g * inv_mod( pb[ t ][ N - 1 - i ], MOD[ t ] ) % MOD[ t ]; } bool ok = false; for( int p = -1; p < 2; ++p ) { for( int q = -1; q < 2; ++q ) { long long x = p * MOD[ 0 ] + nv[ 0 ], y = q * MOD[ 1 ] + nv[ 1 ]; ok |= x == y and x != A[ i ] and abs( x ) <= K and ( i or x ); } } ans += ok; } cout << ans << endl; return 0; }