本来在想其他的题,好像想偏了,不过最后总结找到了标题所对应的公式。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000;
#define lowbit(x) ((x)&(-x))
int n, x;
int c[maxn], a[maxn];
void update(int x, int v)
{
for(int i = x; i <= n; i += lowbit(i))
c[i] += v;
}
int getsum(int x)
{
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i))
ans += c[i];
return ans;
}
int main()
{
int ans = 0;
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++)
a[i] = i;
do{
memset(c, 0, sizeof(c));
printf("当前排列:");
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
int sum = 0;
for(int i = 1; i <= n; i++)
{
update(i, 1);
sum += getsum(n) - getsum(a[i]);
}
printf("逆序对数目:%d\n", sum);
ans += sum;
}while(next_permutation(a+1, a+1+n));
cout << ans << endl;
return 0;
}