鏈接：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;elsea[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; }

　　

轉載于:https://www.cnblogs.com/YDDDD/p/10290848.html

總結

以上是生活随笔為你收集整理的D.出题人的手环的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。