Description：

求所有序列 $a$ 满足“长度为 $n$ 且 $a_i\in[1,A]$ ，并且对于 $i\neq j,a_i\neq a_j$ ”的 $a$ 的乘积的和。

$1\leqslant n\leqslant 500,1\leqslant A\leqslant 10^9$

Solution：

首先根据乘法分配律，我们可以设计出这样一个 $DP$ ： $f[i][j]$ 表示到了第 $i$ 个数，最大的数为 $j$ 的方案数，那么我们可以强制序列递增，反正元素两两不同，最后乘一个阶乘就行了，转移方程为： $$ f[i][j]=j\times\sum_{k=1}^{j-1}f[i-1][k] $$ 但是这样的 $DP$ 是没前途的，我们考虑设 $f[i][j]$ 表示 $i$ 个数最大的小于等于 $j$ 的方案数，把阶乘放进去，转移方程就变成了： $$ f[i][j]=i\times j\times f[i-1][j-1]+f[i][j-1] $$ 这个也可以理解为在 $i$ 个位置中选一个放进去。

这时 $f[i][j]$ 是一个关于 $j$ 的最高次不超过 $2i$ 的多项式，证明的话用数学归纳法结合上面那个递推式可以证明。

于是我们只要暴力 $DP$ 出 $j\in[1,2n]$ 的所有值，然后拉格朗日插值就行了。

感觉这个方法好像通用性很强啊，只要推出来了多项式的性质什么都可以 $O(n^2)$ 求解了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll a,n,MOD;

ll f[510][1010];

ll x[1010],y[1010];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

ll lagrange(ll k)

{

	ll ans = 0;

	for(int i = 1;i <= 2 * n + 1;++i)

	{

		ll res = y[i];

		for(int j = 1;j <= 2 * n + 1;++j)

		{

			if(i == j)continue;

			res = res * (k - x[j] + MOD) % MOD;

			res = res * power((x[i] - x[j] + MOD) % MOD,MOD - 2) % MOD;

		}

		ans = (ans + res) % MOD;

	}

	return ans;

}

int main()

{

	scanf("%lld%lld%lld",&a,&n,&MOD);

	for(int j = 0;j <= 2 * n + 1;++j)f[0][j] = 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= 2 * n + 1;++j)

		{

			f[i][j] = (f[i][j - 1] + f[i - 1][j - 1] * i % MOD * j % MOD) % MOD;

		}

	}

	for(int i = 1;i <= 2 * n + 1;++i)

	{

		x[i] = i;

		y[i] = f[n][i];

	}

	cout << lagrange(a) << endl;

	return 0;

}