D.出题人的手环

链接：https://ac.nowcoder.com/acm/contest/358/D

题意：

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

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

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

思路：

离散化加树状数组，先求出第一种情况的逆序对，之后每次将最后一个数减去比他大的，加上比他小的就是下一个序列的逆序对数。

比赛想到思路了，但是败给了数组，忘记减法中间加上MOD了。

代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200000+10;

const int MOD = 1e9+7;

int data[MAXN];

int a[MAXN];

int c[MAXN];

int n;

struct Node

{

    int v;

    int w;

    bool operator < (const Node & that) const{

        return this->v < that.v;

    }

};

Node node[MAXN];

int lowbit(int x)

{

    return x&-x;

}

void update(int pos,int v)

{

    while (pos <= n)

    {

        c[pos] += v;

        pos += lowbit(pos);

    }

}

int getsum(int pos)

{

    int sum = 0;

    while (pos > 0)

    {

        sum += c[pos];

        pos -= lowbit(pos);

    }

    return sum;

}

int main()

{

    cin >> n;

    {

        for (int i = 1; i <= n; i++)

            cin >> data[i];

        for (int i = 1; i <= n; i++)

        {

            node[i].v = data[i];

            node[i].w = i;

        }

        sort(node + 1, node + n + 1);

        //memset(a,0, sizeof(a));

        memset(c, 0, sizeof(c));

        int pos = 1;

        a[node[1].w] = 1;

        for (int i = 2; i <= n; i++)

        {

            if (node[i].v == node[i - 1].v)//当值相同时，对应的位置为首个位置

                a[node[i].w] = pos;

            else

                a[node[i].w] = ++pos;

        }

        long long ans = 0;

        long long re = 1;

        for (int i = 1; i <= n; i++)

        {

            update(a[i], 1);

            ans = ans % MOD;

            ans += i - getsum(a[i]);

        }

        re = re * ans % MOD;

        for (int i = n; i > 1; i--)

        {

            long long now = getsum(a[i] - 1);

            long long sub = n - now - (getsum(a[i]) - getsum(a[i] - 1));

            ans = ans + now - sub;

            ans = (ans%MOD + MOD)%MOD;

            re = re * ans % MOD;

        }

        re = re % MOD;

        cout << re << endl;

    }

    return 0;

}

巴特西

D.出题人的手环

链接：https://ac.nowcoder.com/acm/contest/358/D

题意：

思路：

代码：

最新文章

热门文章