首页 > 代码库 > 【NOIP2017模拟8.7】好的排列
【NOIP2017模拟8.7】好的排列
正难则反，我们可以考虑下“坏数字”（谷峰）（$a_{i-1} < a_{i}>a_{i+1}$）。数位动规，数字的位置变换我们可以想象成插入，令F[i][j]表示到第i个数字，此时有j个谷峰的合法插入方案数，则第i个数字如果查到j个坏数字的两侧，则不会产生新的“谷峰”，那么有2*j个位置，F[i][j]*(2*j)-->F[i+1][j]，如果插到其他位置，则会产生一个新的“谷峰”（序列两侧可以分别假想有个0），那么有(i-2*j)个位置，F[i][j]*(i-(2*j))-->F[i+1][j+1].初始条件F[1][1]=1，最后$ans=\sum _{i=1}^{n-k}f\left[ n\right] \left[ i\right]$
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #define qaq 1000000007 6 using namespace std; 7 int n,k,q; 8 long long f[3002][3002]; 9 long long ans;10 int main(){11 freopen("permutation.in","r",stdin);12 freopen("permutation.out","w",stdout);13 f[1][1]=1;14 for (int i=2;i<=3000;i++)15 for (int j=1;j<=3000;j++)16 if (!f[i][j])17 f[i][j]=f[i-1][j]*(2*j)%qaq+f[i-1][j-1]*(i-2*(j-1))%qaq;18 scanf("%d",&q);19 while (q--){20 scanf("%d%d",&n,&k);;21 ans=0;22 for (int i=n-k;i>=1;i--)23 ans=(ans+f[n][i])%qaq;24 printf("%lld\n",ans);25 }26 return 0;27 }
（事实上我们可以预处理n，k到3000的值最后再直接累加即可）
【NOIP2017模拟8.7】好的排列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。