做字典网站开发,微信开发网站制作,十大社区团购平台排名,太仓企业网站建设Solution\text{Solution}Solution
纯纯的dp题。 关键在于我们 dp 时只关注不同元素之间的相对大小。
非法情况不易统计#xff0c;考虑转而考虑合法情况再用全排列减。 设计 fif_ifi 为长度为 iii 的排列循环到一直最后也没有跳出的方案数。 枚举最大的元素 iii 放置的位置…Solution\text{Solution}Solution
纯纯的dp题。 关键在于我们 dp 时只关注不同元素之间的相对大小。
非法情况不易统计考虑转而考虑合法情况再用全排列减。 设计 fif_ifi 为长度为 iii 的排列循环到一直最后也没有跳出的方案数。 枚举最大的元素 iii 放置的位置 jjj由于不能跳出jjj 只能放在[i−k1,i][i-k1,i][i−k1,i] 的位置。 那么就有 fi∑ji−k1i(i−1j−1)×fj−1×(j−i)!f_i\sum_{ji-k1}^i \binom{i-1}{j-1}\times f_{j-1}\times (j-i)!fiji−k1∑i(j−1i−1)×fj−1×(j−i)! 解释一下当元素 iii 放在位置 jjj 时选出 j−1j-1j−1 个数放前面方案是(i−1j−1)\binom{i-1}{j-1}(j−1i−1)前面的方案就是 fj−1f_{j-1}fj−1和排列是等价的后面随便放方案就是阶乘。 然后把组合数拆一下变成 fi∑ji−k1i(i−1)!(j−1)!×fj−1f_i\sum_{ji-k1}^i\frac{(i-1)!}{(j-1)!} \times f_{j-1}fiji−k1∑i(j−1)!(i−1)!×fj−1 (i−1)!×∑ji−k1ifj−1(j−1)!(i-1)!\times\sum_{ji-k1}^i\frac{f_{j-1}}{(j-1)!} (i−1)!×ji−k1∑i(j−1)!fj−1 (i−1)!×∑ji−ki−1fjj!(i-1)!\times\sum_{ji-k}^{i-1}\frac{f_{j}}{j!} (i−1)!×ji−k∑i−1j!fj 把后面的东西拿前缀和优化一下即可线性求出 fff 数组。 求出 fff 之后枚举 nnn 所在的位置 iii答案就是 ans∑i1n(n−1i−1)×fi−1×(n−i)!ans\sum_{i1}^n\binom{n-1}{i-1}\times f_{i-1}\times (n-i)!ansi1∑n(i−1n−1)×fi−1×(n−i)!
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 N1e6100;
const int mod1e97;
int n,m,k;
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resx*res%mod;xx*x%mod;k1;}return res;
}
ll jc[N],ni[N];
ll f[N],sum[N];
inline ll C(ll n,ll m){return jc[n]*ni[m]%mod*ni[n-m]%mod;
}
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();kread();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;f[0]1;sum[0]1;for(int i1;in;i){f[i]jc[i-1]*(sum[i-1]mod-(i-k0?sum[i-k-1]:0))%mod;sum[i](sum[i-1]f[i]*ni[i])%mod;}ll ans(0);for(int i1;in;i){(ansf[i-1]*C(n-1,i-1)%mod*jc[n-i]%mod)%mod;}printf(%lld\n,(jc[n]mod-ans)%mod);return 0;
}
/*
*/
