102222I - Bubble Sort

给定n,k询问有多少n的排列满足在进行k轮冒泡排序(这里指的是一个for交换过去)之后形成的排列的最长上升子序列为n-1(即只有一个数不有序)

n,k=50(其实只有O(n))

这傻逼题想了一年，艹

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

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

我们考虑怎么通过b来推出a

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

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

考虑什么样的终态合法：

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

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

3. 中间有一个b_i!=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"; ``````` ``