the solution of Gym102222I

102222I - Bubble Sort

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

We define AA is the permutation of n, and BB is a sequence of n.

BiBi is defined as the number of subscripts that satisfy the condition

k<i and Ak>Aik<iandAk>Ai

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

We consider to use sequence BB to solve the problem, we first prove that for every valid sequence BB, there is exactly one permutation AA corresponding to it.

We consider how to infer AA from BB.

It is very obvious that AnAn (the length of the permutation is n) can be directly infered by BnBn, and An−1An−1 is also easily to know if AnAn is known,and so on. So as long as BB is legal, there is an AA permutation obtained, certificated.

That is to say, for each bubbling, every BiBi greater than 00 is decremented by one, and equal to 00, it remains unchanged.

The transformation of BB is easy to stimulate by the conclusion (Obviously,...).

So we only need to calculate the legal number of sequence of BB.

Consider what final states are legal:

1. All Bi=0Bi=0 (ie AA is ordered)

2. There is a consecutive subsequence of Bi=1Bi=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!=0Bi!=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";