首页 > 其他分享 >[AGC030D] Inversion Sum

[AGC030D] Inversion Sum

时间:2023-08-25 18:12:49浏览次数:57  
标签:Inversion int Sum long base AGC030D 逆序 dp Mod

题目大意

一个长度为 \(n\) 的数列,然后给你 \(q\) 个交换或不交换操作,你可以选择操作或者不操作,问所有情况下逆序对的总和。

答案需要对 \(10 ^ 9 + 7\) 取模。

(\(n\leq 3000\),\(q\leq 3000\))。

思路

这道题非常巧妙。

我们先考虑转化题意,求逆序对数量的期望。

记 \(dp_{i,j}\) 表示 \(a_i>a_j\) 的概率,初始值很好设,直接根据初始给出的排列情况进行赋值。

  • 若 \(a_i>a_j\),则 \(dp_{i,j}=1\);
  • 若 \(a_i < a_j\),则 \(dp_{j,i}=1\)。

考虑如果我们交换 \(x\) 和 \(y\) 的位置,会产生什么影响。对于 \(\forall i,j \in \left[ 1,n \right]\),其中 \(i,j\) 没有与 \(x\) 或 \(y\) 的情况,不会影响 \(dp_{i,j}\) 的值。

记 \(f_{i,j}\) 表示未更改前的 \(dp\) 数组,考虑有 \(x,y\) 的情况,显然有

\[dp_{i,x}=\dfrac{f_{i,x}+f_{i,y}}{2} \]

\[dp_{i,y}=\dfrac{f_{i,x}+f_{i,y}}{2} \]

\[dp_{x,i}=\dfrac{f_{x,i}+f_{y,i}}{2} \]

\[dp_{y,i}=\dfrac{f_{x,i}+f_{y,i}}{2} \]

这道题求的是逆序对的总和,所以答案应当是所有情况数与逆序对数量的期望的乘积。

所以最后答案为

\[2^m \times \sum^{n}_{i=1}\sum^{n}_{j=i+1}dp_{i,j} \]

Code

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int Mod = 1e9 + 7;
const int N = 3050;

int n,m;

int a[N];

long long Pow(long long a ,long long b) {
    long long res = 1 ;
    long long base = a;
    while(b) {
   	    if(b & 1)
   		    res = res * base % Mod;
   	    base = base * base % Mod;
   	    b >>= 1;
   }
   return res;
}

long long Inv(int x) {
    return Pow(x,Mod - 2) % Mod;
}

long long dp[N][N],ans = 0;

signed main() {
    cin >> n >> m;
    for(int i = 1;i <= n; i++) 
        cin >> a[i];
    
    for(int i = 1;i <= n; i++) {
        for(int j = 1;j <= n; j++) {
            if(a[i] > a[j])
                dp[i][j] = 1;
        }
    }

    for(int i = 1,x,y;i <= m; i++) {
        cin >> x >> y;

        for(int i = 1;i <= n; i++) {
            if(i == x || i == y)
                continue;
            
            dp[i][x] = dp[i][y] = (dp[i][x] + dp[i][y]) * Inv(2) % Mod;
            dp[x][i] = dp[y][i] = (dp[x][i] + dp[y][i]) * Inv(2) % Mod;
        }

        dp[x][y] = dp[y][x] = (dp[x][y] + dp[y][x]) * Inv(2) % Mod;
    }

    for(int i = 1;i <= n; i++) 
        for(int j = i + 1;j <= n; j++) 
            ans = (ans + dp[i][j]) % Mod;

    ans = 1ll * ans * Pow(2,m) % Mod;

    cout << ans << "\n";
    return 0;
}

标签:Inversion,int,Sum,long,base,AGC030D,逆序,dp,Mod
From: https://www.cnblogs.com/baijian0212/p/AT_agc030_d.html

相关文章

  • [AGC030D] Inversion Sum 题解
    题意给定一个长度为\(n\)的排列\(a\)和\(m\)个形如\(\left(x,y\right)\)的操作,每次操作可以选择是否交换\(a_x,a_y\),求最终所有形成的排列的逆序对总数。(\(1\len,m\le3000\))。题解考虑转化题意,考虑求出最终总的期望逆序对数,即CF258D。转化答案\[\text{Ans}=......
  • Commit failed (details follow): Working copy text base is corrupt Checksum misma
    问题:提交一个svn文件报错,提交其他文件没有报错解决办法:(网上看了很多方法都解决不了):1、把文件拷贝到svn目录外放着2、把svn目录下文件移除,然后commitsvn3、把目录外的文件拷贝进来,先Add,然后commit就成功了......
  • 什么是 SAP S/4HANA 的 VDM Layering Architecture 的 VDM Comsumption View
    SAPS/4HANA的VDMLayeringArchitecture的VDMConsumptionView在深入探讨"SAPS/4HANA的VDMLayeringArchitecture的VDMConsumptionView"之前,让我们逐步了解这个概念的不同组成部分。SAPS/4HANA:SAPS/4HANA是SAP的下一代企业资源计划(ERP)套件,通过内存数据库和先进的分......
  • Namomo Summer Camp 23 Day 1(GCPC2021)
    NamomoSummerCamp23Day1(GCPC2021)ProblemB:BrexitingandBrentering签到#include<bits/stdc++.h>usingi64=longlong;usingnamespacestd;typedefpair<i64,i64>PII;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr)......
  • Leetcode 1. 两数之和(Two sum)
    题目链接......
  • P1466 Subset Sum
    对于从1∼n的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的求可以划分的方案数1.动态规划longlongmaxval(intn){intsum=(1+n)*n/2;if(sum%2==1)return0;vector<longlong>dp(sum+1)dp[0]=1;//边界方案数为1for(inti......
  • js 计算对象数组中某个字段sum之和
    1、一个字段之和要计算一个对象数组中某个字段的和,你可以使用JavaScript的Array.prototype.reduce()方法。reduce()方法对数组中的每个元素执行一个提供的函数,并将结果累积为单个值。以下是一个示例:假设你有一个对象数组 data,每个对象都有一个 value 字段,你想计算所有对......
  • leetcode-1-two sum(brute force, hash table)
    Wecanusebruteforcetogetit,usetwoforloopiandj,whichi=1:nandj=i:n.However,thetimecomplexityisO(n^2),whichisnotefficient.Usehashtable,thefirstthingisfirststoreeveryelementtotable,thendotraverseagaintolookup......
  • 20230619 java.util.IntSummaryStatistics
    介绍java.util.IntSummaryStatisticspublicclassIntSummaryStatisticsimplementsIntConsumer统计的指标:count,sum,min,average,maxAPI构造器IntSummaryStatistics()IntSummaryStatistics(longcount,intmin,intmax,longsum)publiccombinevoidcombi......
  • [ABC238E]Rcange Sums
    前言一道水得不能再水的题,虽说在图论的题单里,但我真的没有用图,用了并查集就轻松\(AC\)。大意输入\(q\)个\(l,r\),表示知道\(l\)到\(r\)的区间,最后问能不能知道\(0\)到\(n\),能就输出Yes,不能就输出No。思路图论做法:可以把知道\(l\)到\(r\)的区间抽象为从\(l-1\)向\(r\)连一条边......