102222I - Bubble Sort

2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming Contest

We define $$$A$$$ is the permutation of n, and $$$B$$$ is a sequence of n

$$$Bi$$$ is defined as the number of subscripts that satisfy the condition $$$ k<i&&Ak>Ai $$$

Obviously,after a round of bubbling,$$$Bi$$$will minus one (if $$$Bi>0$$$), and $$$Ai$$$ will also move forward one space (i--)(although this is useless)

We consider to use sequence $$$B$$$ to solve the problem, we first prove that for every valid sequence $$$B$$$, there is exactly one permutation $$$A$$$ corresponding to it

We consider how to infer $$$A$$$ from $$$B$$$

It is very obvious that $$$An$$$ (the length of the permutation is n) can be directly infered by $$$Bn$$$, and $$$A n-1$$$ is also easily to know if $$$An$$$ is known,and so on. 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

So we only need to calculate the legal number of sequence of $$$B$$$

Consider what final states are legal:

1. All $$$Bi=0$$$ (ie $$$A$$$ is ordered)

2. There is a consecutive subsequence of $$$Bi=1$$$ in the permutation, and the rest are 0, such as 0 0 1 1 0 (1 4 2 3 5)

3. There is only one $$$Bi!=0$$$ in the permutation, and the others are 0, such as 0 0 2 0 0 (2 3 1 4 5)

I think it is easy to use Dynamic programming to solve this problem, set 3 states is ok

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