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,Biwill 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 sequenceB, 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";