解题报告

抄题解时间到，令 $f(i)$ 表示长度为 $i$ 的答案，则可以得出这样的方程：

$$ f(1)=0,f(i)=\sum_{j=2}^{i}[f(j)+1]\cdot g(i,j)\\ f(i)={\sum_{j=2}^{i-1}[f(j)+1]\cdot g(i,j)+g(i,i)\over1-g(i,i)} $$

其中 $g(i,j)$ 表示随机之后把长度 $i$ 变成长度 $j$ 的概率，很明显：

$$ g(i,j)={h(j)\cdot{i-1\choose j-1}\over i!} $$

其中 $h(j)$ 表示长度为 $j$ 的排列中有多少两两不连续。$i-1\choose j-1$ 是插板解 $\sum_{k=1}^{j}x_k=i$ 即合并的方案数。

现在唯一的问题就是这个 $h(j)$ 的求法，因为正反都很难求，所以考虑容斥：

$$ h(j)=\sum_{k=0}^{j-1}(-1)^k\cdot(j-k)!\cdot{j-1\choose k} $$

连续个数大于等于 $k$ 的方案数是先确定 $k$ 个连续位置，其他乱放，就可以得出上述式子。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=2000,MOD=1e9+7;

int n,f[maxn+5],g[maxn+5][maxn+5],h[maxn+5],fac[maxn+5],INV[maxn+5],C[maxn+5][maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Make(){
    fac[0]=1;for (int i=1;i<=maxn;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=Pow(fac[i],MOD-2);
    for (int i=C[0][0]=1;i<=maxn;C[i++][0]=1) for (int j=1;j<=i;j++) AMOD(C[i][j]=C[i-1][j-1],C[i-1][j]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    Make();scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=0;j<i;j++)
            j&1?AMOD(h[i],MOD-(LL)fac[i-j]*C[i-1][j]%MOD):AMOD(h[i],(LL)fac[i-j]*C[i-1][j]%MOD);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=i;j++)
            g[i][j]=(LL)h[j]*C[i-1][j-1]%MOD*INV[i]%MOD;
    for (int i=2;i<=n;i++){
        for (int j=2;j<i;j++) AMOD(f[i],(LL)(f[j]+1)*g[i][j]%MOD);
        AMOD(f[i],g[i][i]);f[i]=(LL)f[i]*Pow(MOD+1-g[i][i],MOD-2)%MOD;
    }printf("%d\n",f[n]);return 0;
}