题解 P2401 【不等数列】

· · 题解

PS：这片题解重新提交不止是为了防作弊，整篇题解除了图片都被我删掉重写了一遍，因为以前文笔太差，实在让人无法理解，希望管理员大大给个通过，谢谢QwQ

update 2018-12-14：发现自己以前发的题解现在竟然自己都有点看不懂，排名竟然还是第一，愧对大家的赞，于是重新组织了一下语言，改得便于理解了一些

我有两种方法来解这道题，只想看正解的请无视方法一

方法一：找规律（非正经）

用f[i][j]表示i个数恰有j个小于号的排列数，那么打表可得下图

我们会发现，打出来的表与杨辉三角一样，具有左右对称性。我们接下来就开始找规律吧

我们可以大胆猜想一下（反正这不是正经方法），既然这玩意长得跟杨辉三角这么像，那会不会有杨辉三角的一些其他规律呢？

组合数一个非常重要的规律就是它的递推公式C_n^m=C_{n-1}^{m-1}+C_{n-1}^m

在这个三角中有没有出现呢我们发现f[1][0]=1，如果这个式子具有递推性质的话，f[2][0]和f[2][1]只能从f[1][0]这里递推而来。

那么我们写下递推公式：f[i][j]=f[i-1][j-1]+f[i-1][j]，然后继续往后看

我们发现到了f[3][1]这里，这个规律貌似不适用了。

难道不是递推？不可能，这么优美的性质，肯定是对的。

那为什么这里会出现不适用的情况呢？而且不止这里一处，绝大部分都不适用。

我们还能够发现一个规律，\sum_{j=0}^if[i][j]=i*\sum_{j=0}^{i-1}f[i-1][j],也就是第i行的和等于第i-1行的和的i倍

从第i-1行到第i行总的扩大了i倍，那么我们可不可以认为f[i-1][j-1]也扩大了i倍然后将i倍的f[i-1][j-1]分给了f[i][j-1]和f[i][j]。而在杨辉三角中，扩大的i是一个恒定值2，也难怪会出现不适用的情况了

我们将递推公式换一种表示形式：f[i+1][j]+=a*f[i][j],f[i+1][j+1]+=(i+1-a)*f[i][j]

那么我们可以较为轻易地发现f[3][1]中的4恰好平均的来自f[2][0]和f[2][1]

以此类推，多算几个数我们就会发现递推公式中的a为j+1

所以得出递推公式为

f[i+1][j]+=(j+1)*f[i][j],f[i+1][j+1]+=(i-j)*f[i][j]

也可以换回原来的形式

f[i][j]=(j+1)*f[i-1][j]+(i-j)*f[i-1][j-1]

我第一次做就是用的这种玄学的方法哦，做完后又用下面的数学方法推了一遍

-----------------------------------------------手动分割线------------------------------------------------

方法二：数学方法

这是正经方法

我们考虑现在我们已经有了n-1个数的排列，再插入n使其变成n个数的排列

显然，n有n个位置可以选择，我们先来考虑两边的位置。

如果插入到最左边，会造成新的序列比原来多一个大于号

如果插入到最右边，会造成新的序列比原来多一个小于号

其他的位置就是插入到大于号或小于号的位置

如果插入到大于号的位置，删去一个大于号，多一个大于号一个小于号，也就是多一个小于号

如果插入到小于号的位置，删去一个小于号，多一个大于号一个小于号，也就是多一个大于号

我们会发现插入一个数只有多一个小于号和小于号数目不变两种情况

我们用f[i][j]表示i个数恰有j个小于号的排列数

那么显然f[i+1][j]+=(j+1)*f[i][j]，f[i+1][j+1]+=(i-j)*f[i][j]

好了，问题解决了

上代码

先是暴力版（通不过的，这是帮助我打出那张图的版本）

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1005;
int f[maxn],n,ans[maxn];
bool s[maxn];
void dfs(int step){
    if(step>n){
        int sum=0;
        for(int i=1;i<n;i++)sum+=f[i]<f[i+1]?1:0;
        ans[sum]++;
        return;
    }
    for(int i=1;i<=n;i++)
        if(!s[i]){
            s[i]=1;
            f[step]=i;
            dfs(step+1);
            s[i]=0;
        }
}
int main(){
    scanf("%d",&n);
    dfs(1);
    for(int i=0;i<n;i++)printf("%d ",ans[i]);
}

然后上

正常版本

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#ifdef ONLINE_JUDGE
#define printf(o"\n") printf("I AK IOI\n")
#define printf(o) printf("I AK IOI")
#endif
#define ll long long
#define gc getchar
#define maxn 1005
#define mo 2015
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}int n,k,f[maxn][maxn];

int main(){
    n=read();k=read();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)%mo;
            if(j)f[i][j]=(f[i][j]+f[i-1][j-1]*(i-j))%mo;
        }
    printf("%d\n",f[n][k]);
    return 0;
}

复制题解的猜猜代码能过吗（滑稽