题意
一个序列 $ a_1,a_2,\dots,a_n$ 是合法的，当且仅当：
$ a_1,a_2,\dots,a_n$ 都是\([1,k]\)中的整数。
$ a_1,a_2,\dots,a_n$ 互不相等。
一个序列的值定义为它里面所有数的乘积，即 \(a_1\times a_2\times\dots\times a_n\)。
求所有不同合法序列的值的和。
两个序列不同当且仅当他们任意一位不一样。
输出答案对一个数 \(p\) 取余的结果。
\(k≤10^9,n≤500\)。
题解
显然有一个暴力解法：将 \(a\) 排序，算升序的结果，最后乘以 \(n!\)。设 \(f(i,j)\) 表示前 \(i\) 个数，最大值 \(≤j\)，则 \(f(i,j)=j\times f(i-1,j-1)+f(i,j-1)\)。复杂度 \(O(nk)\)。
观察这个形式，\(f(n,x)\) 是关于 \(x\) 的函数。转移式中只有乘法与加法，则是多项式函数。由于 \(n\) 小 \(x\) 大，不难想到求出其次数，再插值解决。
设 \(f(i,x)\) 次数为 \(g(i)\)。转移式左右两边次数相等，则：
前者由于多项式函数差分，\(f(x)-f(x-1)\)的次数比原多项式小 \(1\)。后者显然。
于是得到 \(g(n)=2n\)。于是 \(f(n,x)\) 是关于 \(x\) 的 \(2n\) 次函数，\(Lagrange\) 插值即可。复杂度 \(O(n^2)\)。