E - Guess the Root 拉格朗日差值法+交互

题目传送门

　　题意：告诉你存在一个未知项系数最高为10的$f(x)$，你最多可以有50次询问，每次询问给出一个$x'$，系统会返回你$f(x')$的值，你需要猜一个$x''$，使得$f(x'')=0$，所有运算都是取模1e6+3下进行的。

　　思路：拉格朗日插值法的模板题。yyb聚聚的公式

　　$p(x)=$\sum\limits_{n}^{i=0}$(-1)*p(i)*x*(x-1)*(x-2)*(x-3)*……*(x-n)/((n-i)! * i! * (x-i))$

所以先暴力询问0-10的所有答案，然后判断11-p的答案是否为0即可。

#include<bits/stdc++.h>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const ll p=1e6+;

ll a[],f[],jcinv[],inv[p+];

ll qpow(ll a,ll b){

    ll res=;

    a%=p;

    while(b){

        if(b&)res=res*a%p;

        b>>=;

        a=a*a%p;

    }

    return res;

}

void init(){

    f[]=;

    for(int i=;i<=;i++)f[i]=f[i-]*i%p;

    jcinv[]=qpow(f[],p-);

    for(int i=;i>;i--){

        jcinv[i-]=jcinv[i]*i%p;

    }

    inv[]=;

    for(int i=;i<=p;i++)

    {

        inv[i]=inv[p%i]*(p-p/i)%p;

    }

}

int main(){

    init();

    for(int i=;i<=;i++)

    {

        printf("? %d\n",i);

        fflush(stdout);

        scanf("%lld",&a[i]);

        if(a[i]==){

            printf("! %d\n",i);

            fflush(stdout);

            return ;

        }

    }

    for(int k=;k<p;k++)

    {

        ll up=;

        for(int i=;i<=;i++)up=up*(k-i)%p;

        ll res=;

        for(int i=;i<=;i++)

        {

            ll tep=;

            tep=a[i]*up%p*jcinv[-i]%p*jcinv[i]%p*inv[k-i]%p;

            res=(res+tep*(i%==?:-)+p)%p;

        }

        if(res==){

            printf("! %d\n",k);

            fflush(stdout);

            return ;

        }

    }

    printf("! -1\n");

    fflush(stdout);

}