Top

交互问题


题目链接:https://codeforces.com/contest/1155/problem/E

题意:现在有11个数,a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10。他们组成一个函数fx=a0+a1x+a2x^2+…ak*x^k。现在你可以出50个询问,系统会返回fz mod(10^6+3)。在50次询问之后,你要给出一个x,使fx%mod=0

题解:给出不同的11个x可以得到11个方程,现在有11个方程11个未知数,高斯消元求解即可。求解得到a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,枚举x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=20+7;
const int mod=1000003;
ll a[maxn][maxn],x[maxn]; // a[][]增广矩阵 x[]解集
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int n=11;
void Gauss(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(i!=j){
ll tmp=a[i][i]*qpow(a[j][i],mod-2)%mod;
for(int k=1;k<=n+1;k++) a[j][k]=a[i][k]-a[j][k]*tmp%mod,a[j][k]=((a[j][k]%mod)+mod)%mod;
}
}
for(int i=1;i<=n;i++){
a[i][n+1]*=qpow(a[i][i],mod-2),a[i][n+1]%=mod;
x[i]=a[i][n+1];
}
}
int main(){
int ans=0;
for(int i=1;i<=n;i++){
printf("? %d\n",i);
fflush(stdout);
scanf("%d",&ans);
a[i][12]=ans;
a[i][1]=1;
for(int j=2;j<=n;j++)a[i][j]=a[i][j-1]*(ll)i%mod;
}
Gauss();
int flag=1;
for(ll i=0;i<mod;i++){
ll tt=0;
for(ll j=1;j<=11;j++){
tt=(tt+x[j]*qpow(i,j-1)%mod)%mod;
}
if(tt==0){
flag=0;
printf("! %lld\n",i);
fflush(stdout);
return 0;
}
}
if(flag){
printf("! -1\n");
fflush(stdout);
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址