Angie and Functions

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.8s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Angie is studying functions!

For her homework, she was asked to figure out the coefficients c_1, c_2, \dots, c_N, c_{N+1} in the following function:

f(x)=c_1x^N+c_2x^{N-1}+\dots+c_Nx+c_{N+1} (All the coefficients are integers)

To assist her on this question, her math teacher has allowed her to ask queries in the following form:

Given an integer x, what is f(x)?

However, as he doesn't want to give her too many hints, she can only make up to Q queries.

Angie has just started the year and isn't sure how to approach the problem. Can you help her solve it?

Not only will the answers to your queries be given modulo 10^9+7, your output should be modulo 10^9+7 as well.


For all subtasks,


1 \le N \le 2000

-10^9 \le c_1, c_2, \dots, c_N, c_{N+1} \le 10^9

0 \le x < 10^9+7

Subtask 1 [5%]

-5 \le c_1, c_2, \dots, c_N, c_{N+1} \le 5


Subtask 2 [10%]

-5 \le c_1, c_2, \dots, c_N, c_{N+1} \le 5

N \le 3

Subtask 3 [15%]

N \le 500

Subtask 4 [70%]

No additional constraints.

Interaction Format

The first and only line of input will be the integer N.

After that, you will begin interaction.

To make a query, output ? x where x is an integer that satisfies the constraints for x given above (-10^9 \le x \le 10^9).

Then, you will receive an integer denoting the value of f(x). If at any point you make an invalid query, exceed the maximum query count, or give an x that is out of the limits you will receive 10^9+7 instead. It's guaranteed that 0 \le f(x) < 10^9+7 for any valid x.

Once you've completed the problem, output your answer in the form ! c_1 c_2 ... c_N c_N+1, where c_1, c_2, \dots, c_N, c_{N+1} are the coefficients in f(x). The interactor will give no further output at this point.

Important Notes/Reminders

  • All input and output will be modulo 10^9+7. Be careful of how modulo works with negative numbers (e.g. -4 \bmod (10^9+7) = 1\,000\,000\,003)
  • Always flush after writing to Standard Output
  • If you ever receive 10^9+7 as input, make sure to terminate the program (e.g. exit(0); in C++). Otherwise, you will receive TLE instead of WA

Sample Interaction

Note the following:

  • The sample case here is N=3 where c_1=5,c_2=-4,c_3=2,c_4=1
  • >>> denotes your output. Do not actually print >>>
>>> ? 3
>>> ? 5
>>> ? 1000000004
>>> ! 5 1000000003 2 1

Note the following:

  • The answers are outputted modulo 10^9+7.
  • ? 1000000004 is the equivalent of asking for f(-3). f(-3)=-176 and -176 \bmod (10^9+7)=999\,999\,831


There are no comments at the moment.