Advertisement
Guest User

Untitled

a guest
May 25th, 2016
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MOD1 = 29209;
  6. const int MOD2 = 1e9 + 7;
  7. const int MOD3 = 1e9 + 9;
  8. const int N = 1e5 + 100;
  9.  
  10. long long bigMod (long long a, long long e, long long mod) {
  11.     long long ret = 1;
  12.     while (e) {
  13.         if (e & 1) ret = (ret * a) % mod;
  14.         a = (a * a) % mod;
  15.         e >>= 1;
  16.     }
  17.     return ret;
  18. }
  19.  
  20. long long toInt (string s) {
  21.     bool flag = 0;
  22.     if (s[0] == '-') s.erase(s.begin()), flag = 1;
  23.     long long ret = 0;
  24.     for (int j = 0; j < s.size(); j++) {
  25.         ret *= 10;
  26.         ret += (s[j] - '0');
  27.     }
  28.     if (flag) ret = -ret;
  29.     return ret;
  30. }
  31.  
  32. int n;
  33. long long k;
  34. string s;
  35. int unknown = 0;
  36. long long coeff[N];
  37.  
  38. int main (int argc, char const *argv[]) {
  39.     freopen("input.txt", "r", stdin);
  40.  
  41.     cin.tie(0);
  42.     ios_base::sync_with_stdio(0);
  43.  
  44.     cin >> n >> k;
  45.     int pos = 0;
  46.     for (int i = 0; i <= n; i++) {
  47.         cin >> s;
  48.         if (s[0] == '?') ++unknown;
  49.         else coeff[pos++] = toInt(s);
  50.     }
  51.  
  52.     if (unknown) {
  53.         if (n & 1) cout << "Yes\n";
  54.         else cout << "No\n";
  55.     } else {
  56.         long long value1 = 0, value2 = 0, value3 = 0;
  57.         long long pow1 = 1, pow2 = 1, pow3 = 1;
  58.         for (int i = 0; i < pos; i++) {
  59.             value1 += coeff[i] * pow1, value1 %= MOD1;
  60.             value2 += coeff[i] * pow2, value2 %= MOD2;
  61.             value3 += coeff[i] * pow3, value3 %= MOD3;
  62.             pow1 *= k, pow2 *= k, pow3 *= k;
  63.             pow1 %= MOD1, pow2 %= MOD2, pow3 %= MOD3;
  64.         }
  65.         if (value1 == 0 and value2 == 0 and value3 == 0) cout << "Yes\n";
  66.         else cout << "No\n";
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement