https://www.lydsy.com/JudgeOnline/problem.php?id=2655
以上是对 dp 一小部分打的表。dp[ i ] [ j ] 含义为 前 i 个 数 中 选 j 个 的 价 值 总 和 , 则转移 方程为
dp [ i ] [ j ] = dp [ i -1 ] [ j ]+ dp [ i - 1 ] [ j - 1 ] * j * i . 无非就两中情况，第 j 个 （不是 i） ，（是 i），
前一个是 直接 把 i - 1 个中选 j 个转移过来，后一个的含义是 i - 1 个 选了 j - 1个 第 j 个选 i 那么 之前的价值 就都需要 * i
并且 种 数 也会变多 ， 一共选了 j 个数 那么 排列方式 即为 J！ 种 ，由于前面累乘过来了所以这一次直接只需要* j 即可
但是 由于 m 较大 无法直接 dp 转移求出，根据达标规律发现 其为 dp [ i ] [ j ] 是关于 i 的最高次项 次数 为 2 * j 的 多项式
dp [ j ] [ j ] = j ！ * j ！ 最高次项为 2 * j 次的 归纳 得出 dp [ i ] [ j ]为 2*j次的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1555
ll n,a,mod,dp[maxn][maxn],z,m,ans;
ll qpow(ll a,ll b)
{
ll re=1;
while(b)
{
if(b%2)
re=(re*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return re;
}
int main()
{
scanf("%lld%lld%lld",&a,&n,&mod);
dp[0][0]=1;
for(int i=1; i<=2*n; i++)
{
dp[i][0]=dp[i-1][0];
for(int j=1; j<=n; j++)
dp[i][j]=(dp[i-1][j-1]*i*j%mod+dp[i-1][j])%mod;
}
if(a<=2*n)
{
printf("%lld\n",dp[a][n]);
return 0;
}
for(int i=0; i<=2*n; i++)
{
m=1,z=dp[i][n];
for(int j=0; j<=2*n; j++)
{
if(i==j)continue;
z=(z*(a-j)%mod+mod)%mod;
m=(m*(i-j)%mod+mod)%mod;
}
ans=(ans+z*qpow(m,mod-2)%mod+mod)%mod;
}
printf("%lld\n",ans);
return 0;
}
原文：https://www.cnblogs.com/SDUTNING/p/10261608.html