$\text{Solution}$

神奇題目。
首先可以強制所有的數遞增，最后的答案乘一個 $n!$ 即可。
設 $d{p}_{i,j}$ 表示在 $[1,j]$ 的值域選了 $i$ 個數的答案，不難寫出 dp 轉移：
$$d{p}_{i,j}=d{p}_{i?1,j?1}\times j+d{p}_{i,j?1}$$
答案就是 $d{p}_{n,k}$。
直接暴力做是 $O(nk)$ 的，無法通過。

考慮使用拉格朗日插值優化。
既然要用拉格朗日插值，關鍵就在與證明 $d{p}_{n,k}$ 是一個以 $k$ 為自變量的 $f_n$ 次多項式。

首先又一個較為顯然的結論，若 $g(x)$ 是一個 $k$ 次多項式，那么它的差分 $g(x)?g(x?1)$ 就是一個 $k?1$ 次多項式。
那么回到剛才的轉移式，它也可以寫成：
$$d{p}_{i,j}?d{p}_{i,j?1}=d{p}_{i?1,j?1}\times j$$
考慮多項式次數，也就是：
$$f_n?1=f_{n?1}+1$$
也就是說 $f_n$ 是一個公差為二的等差數列。
又因為有：$d{p}_{n,0}=0,f_0=0$，所以就能得到：
$$f_n=2n$$
$O(n^2)$ 暴力求出前 $n$ 項插值即可，連續值域插值可以前綴和優化到線性。
總復雜度 $O(n^2)$。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=2050; int mod; ll n,m; inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=x*res%mod;x=x*x%mod;k>>=1;}return res; } ll x[N],y[N]; ll jc[N],suf[N],pre[N],ni[N]; ll lagrange(int n,ll *y,ll k){//consecutivek%=mod;jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;ni[n]=ksm(jc[n],mod-2);for(int i=n-1;i>=0;i--) ni[i]=ni[i+1]*(i+1)%mod;pre[0]=1;for(int i=1;i<=n;i++) pre[i]=pre[i-1]*(k-i)%mod;suf[n+1]=1;for(int i=n;i>=1;i--) suf[i]=suf[i+1]*(k-i)%mod;ll res(0);for(int i=1;i<=n;i++){ll add=y[i]*pre[i-1]%mod*suf[i+1]%mod*ni[i-1]%mod*ni[n-i]%mod;if((n-i)&1) add=mod-add;(res+=add)%=mod;}return res; } ll dp[505][1505]; signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifm=read();n=read();mod=read();for(int i=0;i<=2*n+1;i++) dp[0][i]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n*2+1;j++){dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]*j)%mod;}}for(int i=1;i<=2*n+1;i++){y[i]=dp[n][i];}ll res=lagrange(2*n+1,y,m);printf("%lld\n",res*jc[n]%mod);return 0; } /* */

總結

以上是生活随笔為你收集整理的洛谷P4463：calc（dp、拉格朗日插值）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。