資源限制

內存限制：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全排列+歸并排序求逆序數。?