返回题库

黑箱多项式

find the values of all the coefficients

专题
General / 综合
难度
L4

题目详情

有一个黑箱多项式 P(x)P(x)，其系数都满足 ai≥0a_i\ge 0（非负整数）。你可以在任意给定点查询 P(x)P(x) 的值。

最少需要查询多少个点，才能确定全部系数？

英文原题

We consider a polynomial P(x)P(x) which all coefficients are positive (ai⩾0)(a_{i} \geqslant 0) . The polynomial is in a black box and we can only retrieve its value in given points. In how many points do we need to value the polynomial in order to find the values of all the coefficients?

解析

最少需要 2\boxed{2} 个点。

构造方法：

  1. 查询 P(1)P(1)，得到
S=∑iai.S=\sum_i a_i.

于是每个系数都满足 0≤ai≤S0\le a_i\le S。

  1. 再查询 P(S+1)P(S+1)。因为基数 B=S+1B=S+1 严格大于每个“数字” aia_i，所以
P(B)=a0+a1B+a2B2+⋯P(B)=a_0+a_1B+a_2B^2+\cdots

就是该整数在 BB 进制下的唯一展开，其各位数字恰好是 a0,a1,a2,…a_0,a_1,a_2,\ldots。

因此两次查询即可恢复所有系数。

英文解析

The minimum number of points required is 2\boxed{2}.

Construction method:

  1. Query P(1)P(1) to obtain
    S=∑iai.S=\sum_i a_i.
    Thus, each coefficient satisfies 0≤ai≤S0\le a_i\le S.

  2. Query P(S+1)P(S+1). Since the base B=S+1B=S+1is strictly greater than each "digit"aia_i,
    P(B)=a0+a1B+a2B2+⋯P(B)=a_0+a_1B+a_2B^2+\cdots
    represents the unique expansion of this integer in base BB, where the digits are exactly a0,a1,a2,…a_0, a_1, a_2, \ldots.

Therefore, all coefficients can be recovered with just two queries.