手机上怎么做微电影网站,网站被k申诉,国家建设 免费论文期刊网站,wordpress前台打开慢Solution\text{Solution}Solution
神奇题目。 首先可以强制所有的数递增#xff0c;最后的答案乘一个 n!n!n! 即可。 设 dpi,jdp_{i,j}dpi,j 表示在 [1,j][1,j][1,j] 的值域选了 iii 个数的答案#xff0c;不难写出 dp 转移#xff1a; dpi,jdpi−1,j−1jdpi,j−1dp_{i,j…Solution\text{Solution}Solution
神奇题目。 首先可以强制所有的数递增最后的答案乘一个 n!n!n! 即可。 设 dpi,jdp_{i,j}dpi,j 表示在 [1,j][1,j][1,j] 的值域选了 iii 个数的答案不难写出 dp 转移 dpi,jdpi−1,j−1×jdpi,j−1dp_{i,j}dp_{i-1,j-1}\times jdp_{i,j-1}dpi,jdpi−1,j−1×jdpi,j−1 答案就是 dpn,kdp_{n,k}dpn,k。 直接暴力做是 O(nk)O(nk)O(nk) 的无法通过。
考虑使用拉格朗日插值优化。 既然要用拉格朗日插值关键就在与证明 dpn,kdp_{n,k}dpn,k 是一个以 kkk 为自变量的 fnf_nfn 次多项式。
首先又一个较为显然的结论若 g(x)g(x)g(x) 是一个 kkk 次多项式那么它的差分 g(x)−g(x−1)g(x)-g(x-1)g(x)−g(x−1) 就是一个 k−1k-1k−1 次多项式。 那么回到刚才的转移式它也可以写成 dpi,j−dpi,j−1dpi−1,j−1×jdp_{i,j}-dp_{i,j-1}dp_{i-1,j-1}\times jdpi,j−dpi,j−1dpi−1,j−1×j 考虑多项式次数也就是 fn−1fn−11f_n-1f_{n-1}1fn−1fn−11 也就是说 fnf_nfn 是一个公差为二的等差数列。 又因为有dpn,00,f00dp_{n,0}0,f_00dpn,00,f00所以就能得到 fn2nf_n2nfn2n O(n2)O(n^2)O(n2) 暴力求出前 nnn 项插值即可连续值域插值可以前缀和优化到线性。 总复杂度 O(n2)O(n^2)O(n2)。
Code\text{Code}Code
#includebits/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 cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}const int N2050;
int mod;
ll n,m;
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resx*res%mod;xx*x%mod;k1;}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 i1;in;i) jc[i]jc[i-1]*i%mod;ni[n]ksm(jc[n],mod-2);for(int in-1;i0;i--) ni[i]ni[i1]*(i1)%mod;pre[0]1;for(int i1;in;i) pre[i]pre[i-1]*(k-i)%mod;suf[n1]1;for(int in;i1;i--) suf[i]suf[i1]*(k-i)%mod;ll res(0);for(int i1;in;i){ll addy[i]*pre[i-1]%mod*suf[i1]%mod*ni[i-1]%mod*ni[n-i]%mod;if((n-i)1) addmod-add;(resadd)%mod;}return res;
}
ll dp[505][1505];
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmread();nread();modread();for(int i0;i2*n1;i) dp[0][i]1;for(int i1;in;i){for(int j1;jn*21;j){dp[i][j](dp[i][j-1]dp[i-1][j-1]*j)%mod;}}for(int i1;i2*n1;i){y[i]dp[n][i];}ll reslagrange(2*n1,y,m);printf(%lld\n,res*jc[n]%mod);return 0;
}
/*
*/
