hdu 5224 Tom and paper题意：给出一个1~n的排列，求所有字典序比它小的排列的逆序对之和，答案对1e9+7取模。限制：1 <= n <= 100思路：分类讨论1. 全排列的逆序对之和：n!*n*(n-1)/42. 然后遍历每一位，相等的话继续看后面一位，不等的话，看后面小于它的有多少个数，然后乱搞一下。/*hdu 5224 Tom and paper 题意： 给出一个1~n的排列，求所有字典序比它小的排列的逆序对之和，答案对1e9+7取模。 限制： 1 <= n <= 100 思路： 分类讨论 1. 全排列的逆序对之和：n!*n*(n-1)/4 2. 然后遍历每一位，，相等的话继续看后面一位，不等的话，看后面小于它的有多少个数，然后乱搞一下。 */#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;#define LL __int64#define PB push_backconst int N=105;const int MOD=1000000007;LL qpl[N];LL f[N];int a[N];LL inv(LL a,LL m){LL p=1,q=0,b=m,c,d;while(b>0){c=a/b;d=a; a=b; b=d%b;d=p; p=q; q=d-c*q;}return p<0?p+m:p;}void predo(){f[0]=1;for(int i=1;i<N;++i)f[i]=f[i-1]*i%MOD;LL ny4=inv(4,MOD);for(int i=1;i<N;++i){qpl[i]=f[i]*i*(i-1)%MOD*ny4%MOD;}}vector<int> tab[N];bool vis[N];void deal(int id,int n,LL &ans){memset(vis,0,sizeof(vis));if(tab[id].size()==0) return ;LL sum1=0,sum2=0;for(int i=0;i<id;++i){sum1+=tab[i].size();vis[a[i]]=1;}for(int i=0;i<tab[id].size();++i){for(int j=1;j<tab[id][i];++j){if(vis[j]==0) ++sum2;}}ans=(ans+sum1*f[n-1-id]*tab[id].size()+sum2*f[n-1-id])%MOD;ans=(ans+qpl[n-1-id]*tab[id].size())%MOD;}void gao(int n){LL ans=0;for(int i=0;i<n;++i){for(int j=i+1;j<n;++j){if(a[i]>a[j]) tab[i].PB(a[j]);}}for(int i=0;i<n;++i){deal(i,n,ans);}printf("%I64d\n",ans);}void init(){for(int i=0;i<=N;++i)tab[i].clear();}int main(){int n;predo();while(scanf("%d",&n)!=EOF){init();for(int i=0;i<n;++i)scanf("%d",&a[i]);gao(n);}return 0;}
以前我是个爱仰望天空的人，苍蓝的天空总是给我求生的勇气，
