排队时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述T h e _ _ F l a s h The\_\_FlashThe__Flash打游戏太投入了把P L M M PLMMPLMM晾在了一边。为了弥补P L M M PLMMPLMMT h e _ _ F l a s h The\_\_FlashThe__Flash带着P L M M PLMMPLMM和小喵去看电影。电影院人山人海队伍排成一条长长的线两人一喵只能乖乖排队。队伍长度为n nn个体按照队头到队尾的顺序依次编号为1 , 2 , . . . , n 1,2,...,n1,2,...,n其中第i ii个个体的身高为a i a_iai。P L M M PLMMPLMM见状想要出题考验一下T h e _ _ F l a s h The\_\_FlashThe__Flash。一个长度为n nn的序列a aa的逆序对个数定义为满足a i a j ( 1 ≤ i j ≤ n ) a_ia_j (1≤ij≤n)aiaj(1≤ij≤n)的不同( i , j ) (i,j)(i,j)的对数( i 1 , j 1 ) (i_1,j_1)(i1,j1)与( i 2 , j 2 ) (i_2,j_2)(i2,j2)不同当且仅当i 1 ≠ i 2 i_1≠i_2i1i2或j 1 ≠ j 2 j_1≠j_2j1j2。n nn个个体总共有n n\!n种排队方式记P i ( a ) P_i(a)Pi(a)表示序列a aa的第i ii种排队方式c n t ( P i ( a ) ) cnt(P_i(a))cnt(Pi(a))表示P i P_iPi的逆序对个数。P L M M PLMMPLMM想知道∑ i 1 n ! c n t ( P i ( a ) ) ∑_{i1}^{n!}cnt(P_i(a))∑i1n!cnt(Pi(a))由于T h e _ _ F l a s h The\_\_FlashThe__Flash傻乎乎的所以请你帮他回答P L M M PLMMPLMM的问题。输入描述第一行输入一个整数n ( 1 ≤ n ≤ 10 5 ) n (1≤n≤10^5)n(1≤n≤105)。第二行输入n nn个整数表示a 1 , a 2 , ⋯ , a n ( 1 ≤ a i ≤ 10 5 ) a_1,a_2,⋯ ,a_n (1≤a_i≤10^5)a1,a2,⋯,an(1≤ai≤105)。输出描述输出一个整数表示答案由于结果可能太大因此你只需要输出结果对10 9 7 10^971097取模之后的结果。示例1输入3 1 2 3输出9示例2输入7 2 4 4 3 1 1 2输出45360解题思路本题是全排列逆序对总和的经典组合数学问题核心是将所有排列的逆序对总数转化为每一对不等值元素的贡献之和并利用阶乘快速计算。1. 问题等价转化单个排列的逆序对对于长度为n nn的序列逆序对指数对( i , j ) (i,j)(i,j)满足i j ijij且a i a j a_i a_jaiaj。所有排列的逆序对总和考虑所有n ! n!n!种不同排列。对于任意两个位置上的具体元素x xx和y yy值不同在全体排列中x xx出现在y yy前面和后面的次数相等均为n ! / 2 n!/2n!/2。因此每对不相等的元素恰好在一半的排列中构成逆序对贡献n ! / 2 n!/2n!/2次逆序对。值相等的元素永远不会构成逆序对。计算公式令总元素对数S C n 2 S C_n^2SCn2相等元素对内不会产生逆序对。设每个值的出现次数为c 1 , c 2 , … c_1, c_2, \dotsc1,c2,…则值不相等的元素对数为K C n 2 − ∑ C c i 2 K C_n^2 - \sum C_{c_i}^2KCn2−∑Cci2。总逆序对和为Ans K × n ! 2 ( m o d 10 9 7 ) \text{Ans} K \times \frac{n!}{2} \pmod{10^97}AnsK×2n!(mod1097)2. 算法实现预处理阶乘计算f [ i ] i ! m o d m o d f[i] i! \bmod modf[i]i!modmod用于快速得到n ! n!n!和( n − 2 ) ! (n-2)!(n−2)!。统计不等值对数K KK将数组a aa升序排序。对每个元素a i a_iai用二分查找找出严格小于它的元素个数p o s i pos_iposi即lower_bound返回的下标。求和c n t ∑ p o s i cnt \sum pos_icnt∑posi这恰好等于“值不相等的元素对数”K KK因为每对不相等的元素在排序后较小者会被较大者计数一次。计算结果计算p u t C n 2 × ( n − 2 ) ! m o d m o d put C_n^2 \times (n-2)! \bmod modputCn2×(n−2)!modmod这等价于n ! / 2 m o d m o d n!/2 \bmod modn!/2modmod。答案 c n t × p u t m o d m o d cnt \times put \bmod modcnt×putmodmod。特判n 1 n1n1逆序对总数为0 00。3. 复杂度分析时间复杂度排序O ( n log n ) O(n \log n)O(nlogn)二分O ( n log n ) O(n \log n)O(nlogn)或直接双指针O ( n ) O(n)O(n)预处理阶乘O ( n ) O(n)O(n)。总O ( n log n ) O(n \log n)O(nlogn)n ≤ 10 5 n \le 10^5n≤105完全可行。空间复杂度O ( n ) O(n)O(n)存储数组和阶乘。总结利用对称性任意一对不等值元素在全体排列中贡献n ! / 2 n!/2n!/2个逆序对问题转化为统计不等值元素对数。排序后通过二分或双指针可快速求得该对数再乘上n ! / 2 n!/2n!/2即得答案。需注意模运算和n 1 n1n1的特殊情况。代码简要说明阶乘预处理f[1]1递推f[i]f[i-1]*i%mod。输入与排序读入n nn和数组w ww对w ww升序排列。统计不等值对数遍历每个w i w_iwipos lower_bound(w1, wn1, w[i]) - (w1)得到严格小于w i w_iwi的元素个数累加至cnt。答案计算put (n*(n-1)/2) % mod * f[n-2] % mod即n ! / 2 m o d m o d n!/2 \bmod modn!/2modmod。输出cnt * put % mod。边界处理若n 1 n1n1直接输出0 00。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N100012;constll INF1e18;constll M1e610;constll mod1e97;ll n,w[N],f[N*2];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);f[1]1;for(ll i2;iN;i)f[i]f[i-1]*i%mod;cinn;for(ll i1;in;i)cinw[i];sort(w1,wn1);if(n1){cout0;return0;}ll cnt0;for(ll i1;in;i){ll poslower_bound(w1,wn1,w[i])-(w1);cntpos;}ll put(n*(n-1)/2)%mod*f[n-2]%mod;cout(cnt*putmod)%mod;return0;}
排队【牛客tracker 每日一题】
排队时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述T h e _ _ F l a s h The\_\_FlashThe__Flash打游戏太投入了把P L M M PLMMPLMM晾在了一边。为了弥补P L M M PLMMPLMMT h e _ _ F l a s h The\_\_FlashThe__Flash带着P L M M PLMMPLMM和小喵去看电影。电影院人山人海队伍排成一条长长的线两人一喵只能乖乖排队。队伍长度为n nn个体按照队头到队尾的顺序依次编号为1 , 2 , . . . , n 1,2,...,n1,2,...,n其中第i ii个个体的身高为a i a_iai。P L M M PLMMPLMM见状想要出题考验一下T h e _ _ F l a s h The\_\_FlashThe__Flash。一个长度为n nn的序列a aa的逆序对个数定义为满足a i a j ( 1 ≤ i j ≤ n ) a_ia_j (1≤ij≤n)aiaj(1≤ij≤n)的不同( i , j ) (i,j)(i,j)的对数( i 1 , j 1 ) (i_1,j_1)(i1,j1)与( i 2 , j 2 ) (i_2,j_2)(i2,j2)不同当且仅当i 1 ≠ i 2 i_1≠i_2i1i2或j 1 ≠ j 2 j_1≠j_2j1j2。n nn个个体总共有n n\!n种排队方式记P i ( a ) P_i(a)Pi(a)表示序列a aa的第i ii种排队方式c n t ( P i ( a ) ) cnt(P_i(a))cnt(Pi(a))表示P i P_iPi的逆序对个数。P L M M PLMMPLMM想知道∑ i 1 n ! c n t ( P i ( a ) ) ∑_{i1}^{n!}cnt(P_i(a))∑i1n!cnt(Pi(a))由于T h e _ _ F l a s h The\_\_FlashThe__Flash傻乎乎的所以请你帮他回答P L M M PLMMPLMM的问题。输入描述第一行输入一个整数n ( 1 ≤ n ≤ 10 5 ) n (1≤n≤10^5)n(1≤n≤105)。第二行输入n nn个整数表示a 1 , a 2 , ⋯ , a n ( 1 ≤ a i ≤ 10 5 ) a_1,a_2,⋯ ,a_n (1≤a_i≤10^5)a1,a2,⋯,an(1≤ai≤105)。输出描述输出一个整数表示答案由于结果可能太大因此你只需要输出结果对10 9 7 10^971097取模之后的结果。示例1输入3 1 2 3输出9示例2输入7 2 4 4 3 1 1 2输出45360解题思路本题是全排列逆序对总和的经典组合数学问题核心是将所有排列的逆序对总数转化为每一对不等值元素的贡献之和并利用阶乘快速计算。1. 问题等价转化单个排列的逆序对对于长度为n nn的序列逆序对指数对( i , j ) (i,j)(i,j)满足i j ijij且a i a j a_i a_jaiaj。所有排列的逆序对总和考虑所有n ! n!n!种不同排列。对于任意两个位置上的具体元素x xx和y yy值不同在全体排列中x xx出现在y yy前面和后面的次数相等均为n ! / 2 n!/2n!/2。因此每对不相等的元素恰好在一半的排列中构成逆序对贡献n ! / 2 n!/2n!/2次逆序对。值相等的元素永远不会构成逆序对。计算公式令总元素对数S C n 2 S C_n^2SCn2相等元素对内不会产生逆序对。设每个值的出现次数为c 1 , c 2 , … c_1, c_2, \dotsc1,c2,…则值不相等的元素对数为K C n 2 − ∑ C c i 2 K C_n^2 - \sum C_{c_i}^2KCn2−∑Cci2。总逆序对和为Ans K × n ! 2 ( m o d 10 9 7 ) \text{Ans} K \times \frac{n!}{2} \pmod{10^97}AnsK×2n!(mod1097)2. 算法实现预处理阶乘计算f [ i ] i ! m o d m o d f[i] i! \bmod modf[i]i!modmod用于快速得到n ! n!n!和( n − 2 ) ! (n-2)!(n−2)!。统计不等值对数K KK将数组a aa升序排序。对每个元素a i a_iai用二分查找找出严格小于它的元素个数p o s i pos_iposi即lower_bound返回的下标。求和c n t ∑ p o s i cnt \sum pos_icnt∑posi这恰好等于“值不相等的元素对数”K KK因为每对不相等的元素在排序后较小者会被较大者计数一次。计算结果计算p u t C n 2 × ( n − 2 ) ! m o d m o d put C_n^2 \times (n-2)! \bmod modputCn2×(n−2)!modmod这等价于n ! / 2 m o d m o d n!/2 \bmod modn!/2modmod。答案 c n t × p u t m o d m o d cnt \times put \bmod modcnt×putmodmod。特判n 1 n1n1逆序对总数为0 00。3. 复杂度分析时间复杂度排序O ( n log n ) O(n \log n)O(nlogn)二分O ( n log n ) O(n \log n)O(nlogn)或直接双指针O ( n ) O(n)O(n)预处理阶乘O ( n ) O(n)O(n)。总O ( n log n ) O(n \log n)O(nlogn)n ≤ 10 5 n \le 10^5n≤105完全可行。空间复杂度O ( n ) O(n)O(n)存储数组和阶乘。总结利用对称性任意一对不等值元素在全体排列中贡献n ! / 2 n!/2n!/2个逆序对问题转化为统计不等值元素对数。排序后通过二分或双指针可快速求得该对数再乘上n ! / 2 n!/2n!/2即得答案。需注意模运算和n 1 n1n1的特殊情况。代码简要说明阶乘预处理f[1]1递推f[i]f[i-1]*i%mod。输入与排序读入n nn和数组w ww对w ww升序排列。统计不等值对数遍历每个w i w_iwipos lower_bound(w1, wn1, w[i]) - (w1)得到严格小于w i w_iwi的元素个数累加至cnt。答案计算put (n*(n-1)/2) % mod * f[n-2] % mod即n ! / 2 m o d m o d n!/2 \bmod modn!/2modmod。输出cnt * put % mod。边界处理若n 1 n1n1直接输出0 00。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N100012;constll INF1e18;constll M1e610;constll mod1e97;ll n,w[N],f[N*2];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);f[1]1;for(ll i2;iN;i)f[i]f[i-1]*i%mod;cinn;for(ll i1;in;i)cinw[i];sort(w1,wn1);if(n1){cout0;return0;}ll cnt0;for(ll i1;in;i){ll poslower_bound(w1,wn1,w[i])-(w1);cntpos;}ll put(n*(n-1)/2)%mod*f[n-2]%mod;cout(cnt*putmod)%mod;return0;}
