102222I - Bubble Sort

Obviously, if there are Bi numbers k that satisfy the conditionk<i&&Ak>Ai, then after a round of bubbling,the number of kAk>Ai&&k>i will minus one, and Ai will also move forward one space (although this is useless)

We consider Bi to solve the problem, we first prove that for every valid B(Bii), there is exactly one A corresponding to it

We consider how to push A through B

It is very obvious that An can be directly obtained by Bn, and A{n-1} is also obtained after An is obtained, so as long as B is legal, there is an A permutation obtained, certificated

That is to say, for each bubbling, every Bi greater than 0 is decremented by one, and equal to 0, it remains unchanged

Consider what final states are legal:

1. All Bi=0 (ie ordered)

2. There is a Bi=1 in the middle, the rest are 0, such as 0 0 1 1 0 (1 4 2 3 5)

3. There is a Bi!=0 in the middle, the others are 0, such as 0 0 2 0 0 (2 3 1 4 5)

This is obviously dp in the past, set 3 states (all m in the front, in the middle section, all m in the back)

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";