# CFR 639 C. Bear and Polynomials ( Hash )

Problem - C - Codeforces

1 ≤ N ≤ 2e5
abs( K ) ≤ 1e9

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;
}
```