设$n=d_k\ldots d_0$，从而
$$P_n(x)=d_kx^k+\ldots+d_0.$$
所有系数均为非负数，因此显然根只能是非正数。
设r是一个整数根，显然当且仅当n能被10整除时可以有$r=0$，这样的n共有$10^{15}$个。
若$r\neq 0$，则等式$P_n(r)=0$两侧同时模$|r|$可得$d_0$能被$|r|$整除，因而此时r只能取-9到-1之间的值。
注意到$(x+1)(x+2)(x+3)(x+4)$的常数项已经是24，因而$P_n(x)$最多只能有三个互异常的整数根，于是可以用容斥原理计算，考察分别有1个，2个，3个互异整数根的多项式的数量再汇总。
分别用$f_1(k,b,a)$, $f_2(k,b_1,b_2,a_1,a_2)$, $f_3(k,b_1,b_2,b_3,a_1,a_2,a_3)$来表示满足$P_n(a_i)=b_i$的n的数量，若$m=d_k\ldots d_1$，则有$P_m(r)=(P_n(r)-d_0)/r$，因此可以递归计算，最终结果是$1311109198529286$。
注：以下为Python 3代码，因需要cache装饰器作记忆化搜索。
from functools import *
@cache
def f1(n,b,a):
return 0<=b<=9 if n==15 else sum(f1(n+1,(b-m)//a,a) for m in range(n==0,10) if (b-m)%(-a)==0)
@cache
def f2(n,b1,b2,a1,a2):
return 0<=b1==b2<=9 if n==15 else sum(f2(n+1,(b1-m)//a1,(b2-m)//a2,a1,a2) for m in range(n==0,10) if (b1-m)%(-a1)==(b2-m)%(-a2)==0)
@cache
def f3(n,b1,b2,b3,a1,a2,a3):
return 0<=b1==b2==b3<=9 if n==15 else sum(f3(n+1,(b1-m)//a1,(b2-m)//a2,(b3-m)//a3,a1,a2,a3) for m in range(n==0,10) if (b1-m)%(-a1)==(b2-m)%(-a2)==(b3-m)%(-a3)==0)
print(10**15+sum(f1(0,0,-i) for i in range(1,10))-sum(f2(0,0,0,-i,-j) for i in range(1,10) for j in range(i+1,10) if i*j<10)+sum(f3(0,0,0,0,-i,-j,-k) for i in range(1,10) for j in range(i+1,10) for k in range(j+1,10) if i*j*k<10))
|
