题意 一个序列a1,…,an是合法的，当且仅当：
长度为给定的n。
a1,…,an都是[1,A]中的整数。
a1,…,an互不相等。
一个序列的值定义为它里面所有数的乘积，即a1a2…an。
求所有不同合法序列的值的和。
两个序列不同当且仅当他们任意一位不一样。
输出答案对一个数mod取余的结果。
A<=10^9,n<=500，mod<=10^9,并且mod为素数，mod>A>n+1
分析 【动态规划|bzoj 2655: calc dp+拉格朗日插值法】首先考虑最简单的dp式：设f[i,j]表示前i个正整数里选了j个的方案和。显然有f[i,j]=f[i-1,j]+f[i-1,j-1]*i。
f[i,j]其实是一个关于i的次数为2j的多项式（然而我还不会证明，如果有大佬会的话麻烦告诉我）。那么我们就可以求出f[i,n] (1<=i<=n*2+1)，然后根据拉格朗日插值法，答案就是 n!?∑i=12n+1f[i,n]?∏j=1,j!=i2n+1A?ji?j ，直接算即可。
代码
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N=1005;
int x,n,MOD,f[N][N],pre[N],suf[N],inv1[N],inv2[N];
int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y&1) ans=(LL)ans*x%MOD;
x=(LL)x*x%MOD;
y>>=1;
}
return ans;
}int main()
{
scanf("%d%d%d",&x,&n,&MOD);
f[0][0]=1;
for (int i=1;
i<=n*2+1;
i++)
{
f[i][0]=f[i-1][0];
for (int j=1;
j<=n;
j++) f[i][j]=(f[i-1][j]+(LL)f[i-1][j-1]*i)%MOD;
}
pre[0]=suf[n*2+2]=1;
for (int i=1;
i<=n*2+1;
i++) pre[i]=(LL)pre[i-1]*(x-i)%MOD;
for (int i=n*2+1;
i>=1;
i--) suf[i]=(LL)suf[i+1]*(x-i)%MOD;
inv1[0]=inv2[0]=1;
for (int i=1;
i<=n*2+1;
i++) inv1[i]=(LL)inv1[i-1]*ksm(i,MOD-2)%MOD,inv2[i]=(LL)inv2[i-1]*ksm(-i,MOD-2)%MOD;
LL ans=0;
for (int i=1;
i<=n*2+1;
i++) (ans+=(LL)f[i][n]*pre[i-1]%MOD*suf[i+1]%MOD*inv1[i-1]%MOD*inv2[n*2+1-i])%=MOD;
for (int i=1;
i<=n;
i++) ans=(LL)ans*i%MOD;
ans+=ans<0?MOD:0;
printf("%lld",ans);
return 0;
} 推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- LeetCode-28 实现strStr() KMP算法
- leetcode|递归、动态规划--Leetcode(python)