临沭网站建设,仓库管理系统er图,商务网站规划与建设,杭州seo网站哪家好正题
题目链接:https://atcoder.jp/contests/agc030/tasks/agc030_d 题目大意 nnn个数#xff0c;ppp次操作可以选择操作或者不操作#xff0c;询问所有情况下逆序对的总和。 解题思路
转换成期望的问题#xff0c;设fi,jf_{i,j}fi,j表示所有情况下aiaja_ia_jai…正题
题目链接:https://atcoder.jp/contests/agc030/tasks/agc030_d 题目大意
nnn个数ppp次操作可以选择操作或者不操作询问所有情况下逆序对的总和。 解题思路
转换成期望的问题设fi,jf_{i,j}fi,j表示所有情况下aiaja_ia_jaiaj的情况那么对于每次操作有12\frac{1}{2}21的概率交换和不交换可以用dpdpdp转移。最后答案乘上2q2^q2q即可。
时间复杂度O(n2nq)O(n^2nq)O(n2nq) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N3100,XJQ1e97;
ll n,q,a[N],f[N][N],g[N][N];
int main()
{scanf(%lld%lld,n,q);for(ll i1;in;i)scanf(%lld,a[i]);for(ll i1;in;i)for(ll j1;jn;j)f[i][j](a[i]a[j]);ll inv(XJQ1)/2,k1;while(q--){ll l,r;kk*2%XJQ;scanf(%lld%lld,l,r);f[l][r]f[r][l](f[l][r]f[r][l])*inv%XJQ;for(ll i1;in;i){if(il||ir)continue;f[i][l]f[i][r](f[i][r]f[i][l])*inv%XJQ;f[l][i]f[r][i](f[r][i]f[l][i])*inv%XJQ;}}ll ans0;for(ll i1;in;i)for(ll j1;ji;j)(ansf[i][j])%XJQ;printf(%lld,ans*k%XJQ);
}
