[CC-SEABUB]Sereja and Bubble Sort
题目大意：
一个\(n(n\le100)\)个数的排列\(A\)，有两种操作：
- 交换两个相邻元素；
- 等概率随机打乱整个序列。
最多执行\(k(k\le10^{18})\)次操作，使得最后逆序对数量尽可能小，求最后逆序对数量期望值。
单个测试点\(T(T\le100)\)组数据。
思路：
一个基本性质是每交换两个相邻元素都可以消去一个逆序对。
一组询问的答案要么是直接通过交换消去所有的逆序对，要么是通过若干次随机打乱以后再通过交换相邻元素消去逆序对。
对于第一种情况，直接求逆序对即可。答案为\(\min(cnt-k,0)\)。
对于第二种情况，显然打乱以后的排列与\(A\)本身无关，因此考虑动态规划预处理所有答案。
\(f[i][j][k]\)表示排列的长度为\(i\)，有\(j\)个逆序对，再经过不超过\(k\)次操作后，逆序对个数的期望。
\(g[i][j]\)表示排列的长度为\(i\)，再经过不超过\(j\)次操作后，逆序对个数的期望。
\(h[i][j]\)表示排列的长度为\(i\)，逆序对个数为\(j\)的概率。
转移是\(g[i][j]=\sum f[i][k][j]\times h[i][k]\)。
考虑不同取值的\(k\)如何转移。
- \(k\le j\)，在\(j\)步操作内就可以消去所有的逆序对，贡献为\(0\)；
- \(j<k\le\lfloor j+g[i][j-1]\rfloor\)，尽可能地交换，就算不能消去全部，期望也比打乱以后更优。贡献是\(\sum h[i][k]\times(k-j)\)；
- 剩下的情况，重新打乱更优，贡献为\(g[i][j-1]\)。
使用前缀和优化即可。
预处理复杂度\(\mathcal O(n^4)\)，单次询问复杂度\(\mathcal O(n\log n)\)。
源代码：
#include#include #include typedef long long int64;inline int64 getint() { register char ch; while(!isdigit(ch=getchar())); register int64 x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x;}const int N=101,M=4951;int64 k;int n,a[N];double f[N][M],h[N][M],g[N][M];class FenwickTree { private: int val[N]; int lowbit(const int &x) const { return x&-x; } public: void reset() { std::fill(&val[1],&val[n]+1,0); } int query(int p) const { int ret=0; for(;p;p-=lowbit(p)) ret+=val[p]; return ret; } void modify(int p) { for(;p<=n;p+=lowbit(p)) val[p]++; }};FenwickTree t;inline int calc() { int ret=0; t.reset(); for(register int i=n;i>=1;i--) { ret+=t.query(a[i]); t.modify(a[i]); } return ret;}int main() { h[1][0]=1; for(register int i=2;i