洛谷p2401（不等数列）——蒟蒻题解

膜你赛T2——不等数列(洛谷p2401 ps：膜数不一样)

刚开始打了30分的打表（手推不出规律）

因为T1看错题了导致两小时全栽在T1上（

中午开始思考推规律

虽然同机房的说是杨辉三角，但是这方面我做的题不多，没法直接看出来

ps：因为打表时忘了处理0的情况，下意识以为没有<的个数肯定是零，其实还有全大于号的情况啊喂

于是去看题解思路

其实原来也想了是不是通过上面两种临近的情况推过来，所以看完题解豁然开朗，下面写出思路

所以上面的都是废话

首先我们举一个例子

$1<2<3$ 和$1<3>2$这是当$n$等于$3$时的其中两种

当我们处理$n=4$ 时，可以从上面的情况推下来

插入一个$4$,此时$4$为最大值如果插入到两边：左边会增加一个大于号（无关），右边的话会增加一个小于号如果插入中间：在$1<2<3$的$1,2$中间插入，会减少一个小于号并增加一个小于号和一个大于号$1<4>2<3$，即为增加一个大于号，与小于号无关插入中间的第二种：将大于号替换：在$1<3>2$中的$3,2$中间插入，会减少一个大于号并增加一个大于号，一个小于号$1<3<4>2$，即为增加一个小于号总结就是在 右面添加新数 或者在 中间替换大于号 才会改变当前小于号的数量；

得到了规律我们可以慢慢写出递推式（用$f[i][j]$表示$i$个数有$j$个小于号的排列数）：

$f[i+1][j]+=(j+1)\ast f[i][j]$,$f[i+1][j+1]+=(i-j)\ast f[i][j]$

只有这两个式子是因为每个排列都是由小于号少于它一个或者小于号与它相等的排列递推而来

第一个式子中$j+1$是因为包含了所有小于号的位置和最左边的位置

第二个式子中$i-j$为大于号的位置个数

根据这个式子可以很短很快的写出代码

#include<bits/stdc++.h> using namespace std; #define ll long long ll f[1005][1005]; int main(){ ll n,k; cin>>n>>k; f[1][0]=1; for(int i=2;i<=n;++i) for(int j=0;j<=i;++j){ f[i][j]=f[i-1][j]*(j+1)%2012; if(j) f[i][j]=(f[i][j]+f[i-1][j-1]*(i-j))%2012; } cout<<f[n][k]; return 0; }

泪目