CF1155E Guess the Root

Fido_Puppy · 2022-08-29 10:46:10 · 题解

感觉这道交互题好简单……

我这种交互黄题都做不出来的蒟蒻尽然能在 Virtual participation 中过了这题。

CF1155E Guess the Root

由于多项式的次数不超过 10，所以我们只需要询问 11 次就可以把多项式确定下来。

具体就是解一个十一元一次方程组，明显可以用 高斯消元 做。

别的大佬好像用的都是拉格朗日插值，什么都不会的蒟蒻瑟瑟发抖。

这道题由于是在 \mod (10^6 + 3) 下，我们除法就可以改成逆元（不用考虑精度问题啦），并且求零点时只需要 0 \sim 10^6 + 2 暴力枚举就行了。

#include "bits/stdc++.h"

int main() {
    std :: ios_base :: sync_with_stdio(false);
    std :: cin.tie(nullptr);

    typedef long long ll;
    const int mod = 1e6 + 3;

    std :: vector < std :: vector <ll> > a(20, std :: vector <ll> (20));

    auto qpow = [&] (ll x, int p) {
        ll ans = 1;
        while (p) {
            if (p & 1) ans = ans * x % mod;
            x = x * x % mod;
            p >>= 1;
        }
        return ans;
    };

    for (int i = 1; i <= 11; i++) {
        std :: cout << "? " << i - 1 << std :: endl;
        int y; std :: cin >> y;
        ll P = 1ll;
        for (int j = 1; j <= 11; j++) {
            a[i][j] = P;
            P = P * 1ll * (i - 1) % mod;
        }
        a[i][12] = y;
    }

    for (int i = 1; i <= 11; i++) {
        for (int j = i + 1; j <= 12; j++) {
            a[i][j] = a[i][j] * qpow(a[i][i], mod - 2) % mod;
        }
        a[i][i] = 1ll;
        for (int j = 1; j <= 11; j++) {
            if (i != j) {
                for (int k = i + 1; k <= 12; k++) {
                    a[j][k] = (a[j][k] - a[j][i] * a[i][k] % mod + mod) % mod;
                }
                a[j][i] = 0;
            }
        }
    }

    for (int i = 0; i < mod; i++) {
        ll sum = 0, P = 1ll;
        for (int j = 1; j <= 11; j++) {
            sum = (sum + P * a[j][12]) % mod;
            P = P * 1ll * i % mod;
        }
        if (sum == 0) {
            std :: cout << "! " << i << std :: endl;
            return 0;
        }
    }

    std :: cout << "! -1" << std :: endl;

    return 0;
}