Codeforces Round #354 Div2 E. The Last Fight Between Human and AI

問題

解法

K=0 のときや、'?' が含まれるときは場合分けでなんとかなる。'?' が含まれず、Kが0でない時を考える。

$f(x)= a_N x^N + ... +a_1 x+a_0$ がx-kで割り切れるとき、f(k)=0 だから、 $a_N k^N + ... +a_1 k+a_0=0$ である。
よって、 $a_N k^N + ... +a_1 k=-a_0$ より $a_0$ はkの倍数である。
$a_0=b_0 k$ とおいて全体をkで割ると、 $a_N k^(N-1) + ... +a_1 =-b_0$
$a_N k^(N-1) + ... a_2 k =-a_1 -b_0$ より $- a_1 -b_0$ もkの倍数である。
このように再帰的にkの倍数であることが示せるので、kで割っていき、割り切れなければ "No" を返せば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;
  vector<string> a(N + 1);
  int qcnt = 0;
  for (int i = 0; i < N + 1; ++i) {
    cin >> a[i];
    if (a[i] == "?") qcnt++;
  }
  if (K == 0) {
    if (a[0] == "0") {
      cout << "Yes" << endl;
    } else if (a[0] == "?") {
      if ((N + 1 - qcnt) % 2 == 0) {  // AI turn
        cout << "No" << endl;
      } else {
        cout << "Yes" << endl;
      }
    } else {
      cout << "No" << endl;
    }
    return 0;
  }
  if (qcnt > 0) {
    if ((N + 1 - qcnt) % 2 == 0) {  // AI turn
      if (qcnt % 2 == 0) {
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    } else {
      if (qcnt % 2 == 0) {
        cout << "No" << endl;
      } else {
        cout << "Yes" << endl;
      }
    }
    return 0;
  }

  // qcnt==0
  vector<int64_t> b(N + 1);
  for (int i = 0; i < N + 1; ++i) b[i] = atoi(a[i].c_str());

  int64_t sum = 0;
  for (int bb : b) {
    if (sum % abs(K)) {
      cout << "No" << endl;
      return 0;
    }
    sum /= K;
    sum += bb;
  }
  if (sum == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}