0w1

CFR 639 C. Bear and Polynomials ( Hash )

Problem - C - Codeforces

題意:
給你 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;
}