c++ 序列

题目描述

生活中，大多数事物都是有序的，因为顺序的美是最令人陶醉的。所以现在RCDH看了不顺的东西就头痛。所以他想让世界变成有序，可是他只是一个无名小辈，所以只好对数字序列下手。

据他所知序列的混乱程度是由“逆序对”的个数决定，公式是Q=2^n,其中Q是指混乱程度，n是指这个序列“逆序对”的个数。逆序对是这样定义的：假设序列中第i个数是ai，若存在i<j,使得ai>aj，则<ai,aj>就为一个逆序对。

你的任务是给定一个序列，计算其混乱程度Q。这个数可能会比较大，你只需输出Q % 1991 的结果。

输入

第一行，整数n，表示序列中有n个数。

第二行，有n

输出

仅一行，Q mod 1991 的值。

样例输入

4
1 3 4 2

样例输出

4

提示

注释：样例中共有2个逆序对，故Q=2^2=4。所以，Q mod 1991=4。
对于30%的数据 2=<n<=1000
对于100%的数据 2=<n<=50000
数列中的每个数不超过10 000 000的正整数。

Source Code

#include<iostream>
using namespace std;
long long tot,ans,temp[50005],a[50005];
void qsort(int l,int r)//基数排序
{
    if(l==r) return;
    int mid=(l+r)/2;
    qsort(l,mid);
    qsort(mid+1,r);
    int p=l,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])
        {
            tot+=mid-i+1;//逆序对的公式 
            temp[p++]=a[j++];
        }
        else
            temp[p++]=a[i++];
    }
    while(i<=mid) 
        temp[p++]=a[i++];
    while(j<=r) 
        temp[p++]=a[j++];
    for(i=l;i<=r;i++) 
        a[i]=temp[i];
}
int pow(int n)//求幂次方
{
    int ans1=1,a=2;
    while(n>0)
    {
        if(n%2==1)
            ans1=(ans1*a)%1991;
        n/=2; 
        a=(a*a)%1991;
    }
    return ans1;
}
int main()
{
    int n = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
    	cin >> a[i];
    }
    qsort(1,n);
    ans=pow(tot);
    cout<<ans<<endl;//输出
    return 0;
}