蓝桥杯练习系统（算法训练）ALGO-934 序列
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
王神想要知道n的所有排列的逆序对数和，但是他觉得太水了，于是让你算。
输入格式
一行一个整数n
输出格式
一行即答案，对1007取模
样例输入
2
样例输出
1
数据规模和约定
1<=n<=10
#include<iostream>
using namespace std;
const int N=15;
int tmp[N];
int a[N];//mergesort归并排序求逆序数用
int b[N];//dfs全排列用
int n;
bool v[N];
int ans;
int res;
void mergesort(int l,int r){if(l==r) return;int mid=(l+r)/2;mergesort(l,mid);mergesort(mid+1,r);int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(a[i]<=a[j]){tmp[k++]=a[i++];}else{tmp[k++]=a[j++];res+=mid-i+1;}}while(i<=mid) tmp[k++]=a[i++];while(j<=r) tmp[k++]=a[j++];for(int i=l;i<=r;i++) a[i]=tmp[i];
}
void dfs(int x){if(x==n+1){//因为b[i]经过mergesort会被排序，从而影响全排列，所以需要两个数组 for(int i=1;i<=n;i++){
// cout<<b[i]<<" "; a[i]=b[i];}
// cout<<endl;res=0;mergesort(1,n);ans+=res%1007;return ;}for(int i=1;i<=n;i++){if(!v[i]){v[i]=true;b[x]=i;dfs(x+1);v[i]=false;}}
}
int main(){cin>>n;dfs(1);cout<<ans%1007<<endl;
}思路：dfs全排列+归并排序求逆序数。