汕头市队赛SRM 20 T3 灵魂觉醒

背景

自从芽衣、布洛妮娅相继灵魂觉醒之后，琪亚娜坐不住了。自己可是第一个入驻休伯利安号的啊！于是她打算去找德丽莎帮忙，为她安排了灵魂觉醒的相关课程。

第一天，第一节课。

“实现灵魂觉醒之前，你需要先将自己的崩坏能按顺序排好……”

“诶诶，这个要怎么做呢？”算法课没认真听讲也是没有办法的嘛。

于是，琪亚娜设(xia)计(bian)了一套自己的排序方法。

描述

我们可以用n张卡片代表崩坏能，上面恰好写了1到n。

一开始这些卡片是随机排列的，然后为了把它们从小到大排好序，进行如下操作：

①如果卡片已经按1到n排好序，结束操作。

②观察现有排列，如果某一个大于1的区间内的数是顺序加一的，就把这个区间内的卡片粘起来，它们在以后的操作中不会分开。（比如15234这个排列会把234粘起来）

③把所有卡片随机排列（粘在一起的不分开），然后回到①。

恰好路过的符华对这种排序方法非常感兴趣，希望知道它的期望复杂度。于是求期望进行③操作的次数的任务就交给你了。答案对1e9+7取模。

输入格式

一个不超过2000的整数n。

输出格式

一个整数，答案对1e9+7取模后的结果。

样例输入

样例输出

333333338

数据范围与约定

测试点	n
1	1
2	5
3	8
4	10
5	13
6	<=1000
7	<=1000
8	<=2000
9	<=2000
10	<=2000

样例解释

n=3时的精确值是 $\frac{7}{3}=2.33333...$

后记：

琪亚娜·卡斯兰娜：你们是怎么排序的啊？

雷电芽衣：有个库函数叫sort来着……

布洛妮娅：对，挺快的。

————————————————————————————

这题一开始我想着暴力 ans[x]=sigma g[x][y]*ans[y]

g[x][y]表示长度为x的排列排一次之后缩成y段的概率

g[x][y]可以暴力算不过后来打表发现是个组合数然后就可以A辣

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=2e3+,mod=1e9+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k;

int g[M][M];

LL w[M],inv[M];

LL pmod(LL a,LL b){

    int ans=;

    while(b){

        if(b&) ans=ans*a%mod;

        b>>=; a=a*a%mod;

    }

    return ans;

}

void prepare(){

    w[]=; for(int i=;i<=n;i++) w[i]=w[i-]*i%mod;

    inv[n]=pmod(w[n],mod-);

    for(int i=n;i;i--) inv[i-]=inv[i]*i%mod;

}

int f[M],v[M],s[M],ans[M];

void P(int &x){x=(x%mod+mod)%mod;}

int main(){

    n=read(); prepare();

    for(int j=;j<=n;j++){

        g[j][j]=w[j]-s[j]; P(g[j][j]);

        for(int i=j+;i<=n;i++){

            g[i][j]=g[j][j]*(w[i-]*inv[j-]%mod*inv[i-j]%mod)%mod; P(g[i][j]);

            s[i]+=g[i][j]; P(s[i]);

        }

    }

    ans[]=;

    for(int i=;i<=n;i++){

        LL ly=;

        for(int j=;j<i;j++) ly=(ly+1LL*g[i][j]*inv[i]%mod*(ans[j]+)%mod)%mod;

        ans[i]=((ly+g[i][i]*inv[i]%mod)*pmod((-g[i][i]*inv[i]%mod+mod)%mod,mod-))%mod;

    }printf("%d\n",ans[n]);

    return ;

}

巴特西