题解 CF1155E 【Guess the Root】
officeyutong
2019-04-23 11:14:25
首先看到模数只有$10^6+3$,所以我们可以考虑通过某些手段搞出来这个多项式然后暴力枚举所有数带进去检验是否是根。
至于如何搞出来这个多项式？
假设多项式的次数为k,那么我们可以搞出来k个点值然后高斯消元\拉格朗日插值。
关于确定多项式的次数？k次多项式在连续值域上的k+1阶差分全都是0.
所以把1-50的值求出来后差分检验一下多项式次数即可。
```cpp
#include <algorithm>
#include <cstring>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using int_t = long long int;
using pair_t = std::pair<int_t, int_t>;
using std::cin;
using std::cout;
using std::endl;
const int_t mod = 1e6 + 3;
const int_t LARGE = 1e5;
int_t power(int_t base, int_t index) {
const int_t phi = mod - 1;
index = (index % phi + phi) % phi;
int_t result = 1;
while (index) {
if (index & 1) result = result * base % mod;
index >>= 1;
base = base * base % mod;
}
return result;
}
void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {
static int_t Cx[LARGE];
std::fill(Cx, Cx + 1 + n + m, 0);
for (int_t i = 0; i <= n; i++) {
for (int_t j = 0; j <= m; j++) {
Cx[i + j] = (Cx[i + j] + A[i] * B[j] % mod) % mod;
}
}
std::copy(Cx, Cx + 1 + n + m, C);
}
void poly_div(const int_t* A, int_t n, const int_t* B, int_t m, int_t* Q) {
static int_t R[LARGE];
std::copy(A, A + 1 + n, R);
for (int_t i = n - m; i >= 0; i--) {
int_t Qx = R[i + m] * power(B[m], -1) % mod;
Q[i] = Qx;
for (int_t j = m; j >= 0; j--) {
R[i + j] = (R[i + j] - B[j] * Qx % mod + 2 * mod) % mod;
}
}
}
int main() {
std::vector<pair_t> vtxs;
std::vector<int_t> vec;
for (int_t i = 1; i <= 50; i++) {
cout << "? " << i << endl;
cout.flush();
int_t x;
cin >> x;
vec.push_back(x);
vtxs.push_back(pair_t(i, x));
}
//差分
int_t count = 0;
while (true) {
for (int_t i = 0; i < vec.size() - 1; i++)
vec[i] = (vec[i + 1] - vec[i] + mod) % mod;
vec.pop_back();
count++;
#ifdef DEBUG
cout << "diff " << count << " ok ";
for (int_t x : vec) cout << x << " ";
cout << endl;
#endif
if (std::count(vec.begin(), vec.end(), 0) == vec.size()) {
break;
}
}
while (vtxs.size() > count) vtxs.pop_back();
#ifdef DEBUG
cout << "count = " << count << endl;
for (auto x : vtxs) cout << x.first << " " << x.second << endl;
#endif
static int_t prod[LARGE];
prod[0] = 1;
for (const auto& kvp : vtxs) {
int_t B[] = {mod - kvp.first, 1};
poly_mul(prod, vtxs.size(), B, 1, prod);
}
static int_t result_poly[LARGE];
for (const auto& kvp : vtxs) {
int_t x, y;
std::tie(x, y) = kvp;
int_t coef = y;
int_t prod2 = 1;
for (int_t i = 0; i < vtxs.size(); i++) {
if (vtxs[i].first != x) {
prod2 = prod2 * (x - vtxs[i].first + mod) % mod;
}
}
coef = coef * power(prod2, -1) % mod;
static int_t curr[LARGE];
int_t B[] = {mod - x, 1};
poly_div(prod, vtxs.size(), B, 1, curr);
for (int_t i = 0; i <= vtxs.size(); i++) {
result_poly[i] = (result_poly[i] + coef * curr[i] % mod) % mod;
}
}
// for (int_t i = 0; i <= vtxs.size(); i++) cout << result_poly[i] << " ";
// cout << endl;
const auto subs = [&](int_t x) {
int_t result = 0, pow = 1;
for (int_t i = 0; i <= vtxs.size() - 1; i++) {
result = (result + pow * result_poly[i] % mod) % mod;
pow = pow * x % mod;
}
return result;
};
for (int_t i = 0; i < mod; i++) {
if (subs(i) == 0) {
cout << "! " << i << endl;
cout.flush();
return 0;
}
}
cout << "! -1" << endl;
return 0;
}
```