Next K Permutation

3457: Next K Permutation

时间限制: 1 Sec 内存限制: 128 MB
提交: 4 解决: 4
[提交] [状态] [讨论版] [命题人:admin]

题目描述

n 个数有 n! 种全排列情况，对所有排列排序后求第 L 个到第 R 个排列中逆序对数量之和。
逆序对定义（摘自 wiki）：

设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i,j 使得 1≤i<j≤n 而且 Ai>Aj，则 (Ai,Aj) 这一个有序对称为 A 的一个逆序对，也称作逆序。逆序对的数量称作逆序数。

输入

第一行 case 数量 T。
接下来每一行有 3 个数，n,L,R (3≤n≤12,1≤L≤R≤10⁹)。

输出

输出逆序对总数。

样例输入

复制样例数据

3

3 3 5

6 720 720

8 14625 17743

样例输出

提示

样例 1 说明：
3 个数所有排列排序后及其逆序对个数：
(1,2,3): 0;
(1,3,2): 1;
(2,1,3): 1;
(2,3,1): 2;
(3,1,2): 2;
(3,2,1): 3.
第 3 个到第 5 个排列逆序对数量之和为 1+2+2=5。

来源/分类

2017 华东理工上海高校邀请赛

题解：详见代码！！！

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll jie_cheng[],ni_xu_shu[];

 void init()

 {

     jie_cheng[]=ni_xu_shu[]=ni_xu_shu[]=;

     jie_cheng[]=;

     for(ll i=;i<=;i++)

     {

         jie_cheng[i]=jie_cheng[i-]*i;

         ni_xu_shu[i]=jie_cheng[i-]*((i-)*i/)+ni_xu_shu[i-]*i;//长度为i的序列（每个数字都不同）所有排列的逆序数总和

     }

 }

 ll solve(int n,ll k)

 {

     ll res=;

     int prefix[];

     for(int i=;i<=n;i++)//枚举前缀长度

     {

         for(int j=;j<=n;j++)//枚举前缀元素

         {

             bool flag=true;

             for(int s=;s<i;s++)

             {

                 if(prefix[s]==j)//出现过的元素就不能再出现

                 {

                     flag=false;

                     break;

                 }

             }

             if(!flag) continue;

             prefix[i]=j;

             if(k<jie_cheng[n-i]) break;

             else

             {

                 k-=jie_cheng[n-i];

                 res+=ni_xu_shu[n-i];

                 ll cnt=;

                 for(int s=;s<=i;s++)

                 {

                     for(int l=s+;l<=i;l++)

                     {

                         if(prefix[s]>prefix[l])

                         {

                             cnt++;

                         }

                     }

                 }

                 int tmp[];

                 for(int s=;s<=n;s++) tmp[s]=;

                 for(int s=;s<=i;s++) tmp[prefix[s]]=;

                 for(int s=;s<=n;s++)

                 {

                     for(int l=;l<=s;l++)

                     {

                         if(tmp[s]== && tmp[l]==)

                             cnt++;

                     }

                 }

                 res+=jie_cheng[n-i]*cnt;

             }

         }

     }

     return res;

 }

 int main()

 {

     init();

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int n;

         ll l,r;

         scanf("%d %lld %lld",&n,&l,&r);

         printf("%lld\n",solve(n,r)-solve(n,l-));

     }

     return ;

 }

秒客网