第一ppt模板网站,电商创业怎么做,建站公司怎么备案,企业网站模板价格题目链接
Atcoder方向 Luogu方向
题目解法
妙妙题#xff01;#xff01;#xff01; 考虑一个神奇的转化#xff0c;把方案求和变成求 i , j i,j i,j 位置是逆序对的概率 最后的答案就是 2 q ∗ ∑ f i , j 2^q*\sum f_{i,j} 2q∗∑fi,j 考虑 f i , j f_{i,j} fi,…题目链接
Atcoder方向 Luogu方向
题目解法
妙妙题 考虑一个神奇的转化把方案求和变成求 i , j i,j i,j 位置是逆序对的概率 最后的答案就是 2 q ∗ ∑ f i , j 2^q*\sum f_{i,j} 2q∗∑fi,j 考虑 f i , j f_{i,j} fi,j 为 i , j i,j i,j 为逆序对的概率 考虑每次交换 x , y x,y x,y 只会修改 f x , ? , f ? , x , f y , ? , f ? , y f_{x,?},\;f_{?,x},\;f_{y,?},\;f_{?,y} fx,?,f?,x,fy,?,f?,y一共 O ( n ) O(n) O(n) 个值 转移可以考虑交换不交换的概率都是 1 2 \frac{1}{2} 21 需要对于 f x , y , f y , x f_{x,y},\;f_{y,x} fx,y,fy,x 特判不过这都是细节主要还是把求和转化为求概率这一关键步骤 时间复杂度 O ( n q ) O(nq) O(nq)
#include bits/stdc.h
using namespace std;
const int N3100,P1e97,iv2500000004;
int n,q,a[N],f[N][N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int main(){nread(),qread();for(int i1;in;i) a[i]read();for(int i1;in;i) for(int j1;jn;j) f[i][j]a[i]a[j];for(int i1;iq;i){int xread(),yread();for(int i1;in;i){if(ix||iy) continue;int val(1ll*f[x][i]*iv21ll*f[y][i]*iv2)%P;f[x][i]f[y][i]val;val(1ll*f[i][x]*iv21ll*f[i][y]*iv2)%P;f[i][x]f[i][y]val;}int val(1ll*f[x][y]*iv21ll*f[y][x]*iv2)%P;f[x][y]f[y][x]val;}int ans0;for(int i1;in;i) for(int ji1;jn;j) ans(ansf[i][j])%P;for(int i1;iq;i) ansans*2%P;printf(%d,ans);return 0;
}
/*
f[i][j]:a[i]a[j]的期望
*/
