HDU 5225 Tom and permutation

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5225
题意传送门：http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=580&pid=1002

题目翻译

Tom学会了通过写程序求出一个1-n的排列的逆序对数，但他的老师给了他一个难题：
给出一个1-n的排列，求所有字典序比它小的1-n的排列的逆序对数之和。
Tom一时不知道该怎么做，所以他来找你帮他解决这个问题。
因为数可能很大，答案对${10}^{9}+7$取模。

题解

我们首先预处理出N的全排列数量，在预处理出N的所有全排列中逆序对数量，这些都是可以递推的。
然后我们从前往后做。
首先对于某一位，如果选比这一位小的数字，那么之后是可以随意排列的。
那么答案就要加上这一位之前所有固定的数字对于后面的逆序对数量后面的全排列，再加上枚举的这一位数字对于后面的逆序对数量全排列数量，再加上后面所有全排列中的逆序对数量。
如果这一位选择相同的数字，那么之后的一定要选择小于等于其才可以，那么按之前的方法处理下一位即可。

代码

#include<cstdio>
#include<cstring>
using namespace std;
const long long Mod=1e9+7;
const int Maxn=100;
int n;
int num[Maxn+5];
long long Ans=0;
long long sum[Maxn+5];
bool vis[Maxn+5];
inline int lowbit(int x){
    return x&-x;
}
inline void add(int x,long long val){
    for (int i=x;i<=100;i+=lowbit(i))
        sum[i]+=val;
}
inline long long get(int x){
    int ret=0;
    for (int i=x;i;i-=lowbit(i))
        ret+=sum[i];
    return ret;
}
long long fac[Maxn+5];
long long rev[Maxn+5];
inline void init(){
    fac[0]=0;
    fac[1]=1;
    for (int i=2;i<=Maxn;i++)
        fac[i]=fac[i-1]*(long long)i%Mod;
    //for (int i=0;i<=Maxn;i++)
    //  printf("%I64d\n",fac[i]);
    rev[2]=1;
    for (int i=3;i<=Maxn;i++){
        rev[i]=rev[i-1]*(long long)i%Mod+(long long)i*(long long)(i-1)/(long long)2*fac[i-1];
        rev[i]%=Mod;
    }
}
inline void solve(){
    for (int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    memset(sum,0,sizeof(sum));
    memset(vis,false,sizeof(vis));
    Ans=0;
    long long rate=0;
    for (int i=1;i<=n;i++){
        for (int now=1;now<=num[i]-1;now++){
            if (vis[now]) continue;
            long long cnt=0;
            for (int j=1;j<=now-1;j++) if (!vis[j]) cnt++;
            //printf("Pos=%d Choose:%d Lower:%I64d RateLower:%I64d Rev:%I64d\n",i,now,cnt*fac[n-i],rate*fac[n-i],rev[n-i]);
            Ans=(Ans+(rate+cnt)*fac[n-i]%Mod)%Mod;
            Ans=(Ans+rev[n-i])%Mod;
        }
        for (int j=1;j<=num[i]-1;j++) if (!vis[j]) rate++;
        //printf("Pos=%d Rate=%I64d %I64d\n",i,rate,Ans);
        vis[num[i]]=true;
    }
    printf("%I64d\n",Ans);
}
int main(){
    init();
    while(scanf("%d",&n)!=EOF)
        solve();
    return 0;
}

#include<cstdio>

#include<cstring>

using namespace std;

const long long Mod=1e9+7;

const int Maxn=100;

int n;

int num[Maxn+5];

long long Ans=0;

long long sum[Maxn+5];

bool vis[Maxn+5];

inline int lowbit(int x){

return x&-x;

}

inline void add(int x,long long val){

for (int i=x;i<=100;i+=lowbit(i))

sum[i]+=val;

}

inline long long get(int x){

int ret=0;

for (int i=x;i;i-=lowbit(i))

ret+=sum[i];

return ret;

}

long long fac[Maxn+5];

long long rev[Maxn+5];

inline void init(){

fac[0]=0;

fac[1]=1;

for (int i=2;i<=Maxn;i++)

fac[i]=fac[i-1]*(long long)i%Mod;

//for (int i=0;i<=Maxn;i++)

// printf("%I64d\n",fac[i]);

rev[2]=1;

for (int i=3;i<=Maxn;i++){

rev[i]=rev[i-1]*(long long)i%Mod+(long long)i*(long long)(i-1)/(long long)2*fac[i-1];

rev[i]%=Mod;

}

inline void solve(){

for (int i=1;i<=n;i++)

scanf("%d",&num[i]);

memset(sum,0,sizeof(sum));

memset(vis,false,sizeof(vis));

Ans=0;

long long rate=0;

for (int i=1;i<=n;i++){

for (int now=1;now<=num[i]-1;now++){

if (vis[now]) continue;

long long cnt=0;

for (int j=1;j<=now-1;j++) if (!vis[j]) cnt++;

//printf("Pos=%d Choose:%d Lower:%I64d RateLower:%I64d Rev:%I64d\n",i,now,cnt*fac[n-i],rate*fac[n-i],rev[n-i]);

Ans=(Ans+(rate+cnt)*fac[n-i]%Mod)%Mod;

Ans=(Ans+rev[n-i])%Mod;

}

for (int j=1;j<=num[i]-1;j++) if (!vis[j]) rate++;

//printf("Pos=%d Rate=%I64d %I64d\n",i,rate,Ans);

vis[num[i]]=true;

}

printf("%I64d\n",Ans);

}

int main(){

init();

while(scanf("%d",&n)!=EOF)

solve();

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑