102222I - Bubble Sort

非常显然的是，如果一个排列中的数Ai前面有Bi(Bi0)个数比Ai大，那么在一轮冒泡之后，Ai前面比Ai大的数会少1(Bi-1)，而Ai也会向前前进一格（这个没啥用）

我们考虑通过Bi来解决问题，我们先证明一下对于每个合法的B(Bii)，有且只有一个A与它相对应

我们考虑怎么通过B来推出A

非常显然An可以直接通过Bn求出，求出An之后A{n-1}也同样求出，所以只要B合法就有一个A排列求出了,证毕

也就是说，对于每一次冒泡，每一个大于0的Bi减一,等于0则不变

考虑什么样的终态合法：

1. 所有Bi=0(即有序)

2. 中间有一段Bi=1,其他的都是0 比如说0 0 1 1 0(1 4 2 3 5)

3. 中间有一个Bi!=0,其他的都是0 比如说0 0 2 0 0(2 3 1 4 5)

这个显然是dp过去就可以了，设3个状态(前面全m，处于中间段，后面全m)

memset(dp,0,sizeof(dp));
    int ans2=0;
    cin>>n>>m>>mod;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        if(i<=m+1){
            (dp[i][0]+=dp[i-1][0]*(i))%=mod;
        }
        else{
            (dp[i][0]+=dp[i-1][0]*(m+1))%=mod;
            (dp[i][1]+=dp[i-1][0]+dp[i-1][1])%=mod;
            (dp[i][2]+=dp[i-1][1]*(m+1)+dp[i-1][2]*(m+1)+dp[i-1][0]*max(0ll,i-1-(m+1)))%=mod;
        }
    }
    int ans=0;
    for(int i=0;i<3;i++)ans+=dp[n][i];
    cout<<"Case #"<<ts<<": "<<ans%mod<<"\n";