题目链接(https://ac.nowcoder.com/acm/contest/358/D)

题目描述

出题人的妹子送了出题人一个手环,这个手环上有 n 个珠子,每个珠子上有一个数。

有一天,出题人和妹子分手了,想把这个手环从两个珠子间切开,并按顺时针顺序展开成一条链。

可以发现,这条链一共有 n 种可能性。求这 n 种可能性的逆序对数之积模 1000000007。

输入描述:

第一行一个数 n,表示珠子个数。

接下来一行 n 个数,以顺时针顺序给出每个珠子上的整数

样例输入

4

1 3 2 3

样例输出

24

备注

n<=200000,-10^9 <=珠子上的整数 <= 10^9。

题目就是求这n个顺时针排列的逆序数乘积,那么重点就是求逆序数啦,首先求出第一个排列的逆序数,看一下数据范围,n方肯定不行,那么考虑离散化加树状数组N*logN,求出逆序数之后,再从后向前遍历这个数组,考虑每一次的排列的变化,相当于将最后一个数移到第一个位置,那么这个数移动之后造成的逆序数的变化可以O(1)计算出来的,然后每一次的逆序数乘在一起就好啦,嘤嘤嘤,具体实现看我代码qwq

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 1010100
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll __int64
#define INF 0x7fffffff
#define cs(s) freopen(s,"r",stdin)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-10
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
//head
LL sum[200001],tree[200001],mod=1000000007,vis[200001],a[200001],b[200001];
int n;
void add(int t){//树状数组更新
for(int i=t;i<=n;i+=(i)&(-i))tree[i]+=1,tree[i]%=mod;
}
LL que(int t){//树状数组求和,返回的是1-t的和
LL q=0;
for(int i=t;i;i-=(i)&(-i))q+=tree[i],q%=mod;
return q;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-b-1;//离散化操作
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
vis[a[i]]++;
}
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+vis[i];//记录1-i的个数和
LL op=0;
for(int i=1;i<=n;i++){//树状数组求逆序数
add(a[i]);
op+=que(n)-que(a[i]);
op%=mod;
}
LL tt=op;
for(int i=n;i>=2;i--){
tt+=(sum[a[i]-1]-sum[n]+sum[a[i]]+1000ll*mod)%mod;//移动后的逆序数变化
tt%=mod;
op*=tt;
op%=mod;
}
cout<<op<<endl;
return 0;
}
05-11 19:50