• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021杭电多校(二)I love permutation(逆序数的奇偶性)

admin

11月 28, 2021

题目链接:HDU多校第二场 – Virtual Judge (vjudge.net)

总体来说此题的核心要素是求逆序数的奇偶性,奈何数据是1e18所以搞了半天也没搞懂该怎么做。

题解中给出的做法也不是很清楚有待后续学习,其中给出的公式貌似可以计算逆序数的奇偶性(背下来就完事了)

有大佬看懂了题解中sgn(Π)到后面的公式如何得出的话欢迎留言!

 题解做法

 1 //题解代码
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define LL long long
 5 #define LD long double
 6 #define ull unsigned long long
 7 const LL N=5e5+10;
 8 const LL INF=1e18;
 9 LL a,P,b;
10 int cnt=0;
11 void init(){
12     return;
13 }
14 
15 void add(LL &x,LL y){
16     x+=y;if(x>=P)x-=P;
17 }
18 
19 LL mul(LL x,LL y){
20     LL re=0;
21     while(y){
22         if(y&1) add(re,x);
23         add(x,x);y>>=1;
24     } 
25     return re;
26 }
27 
28 inline long long Mul(long long x,long long y){
29     long long tmp=(x*y-(long long)((long double)x/P*y+1.0e-8)*P);
30     return (tmp+P)%P;
31 }
32 
33 LL qpow(LL x,LL y){
34     LL re=1,re2;
35     while(y){
36         if(y&1) {
37             re=Mul(re,x);
38         }
39         x=Mul(x,x);
40         y>>=1;
41     }
42     return re;
43 }
44 
45 void MAIN(){
46     scanf("%lld%lld",&a,&P);
47     b=qpow(a,(P-1)/2);
48     if(b==1) {
49         puts("0");
50     }
51     else if(b==P-1) {
52         puts("1");
53     }
54     else{
55     //    cout<<a<<" "<<P<<" "<<b<<endl;
56         ++cnt;
57     }
58     return;
59 }
60 int main(){
61     freopen("1.in","r",stdin);
62     freopen("1.out","w",stdout);
63     init();
64     int ttt=1;scanf("%d",&ttt);
65     while(ttt--) MAIN();
66     //cout<<cnt<<endl;
67     return 0;
68 }
69 /*
70 
71 */
72  

View Code

 2021.7.25续

经过评论区友人的指点,看了这篇博客大致搞懂了其中的转化,感谢各位!

(1条消息) [hdu多校] I love permutation_Lupin123123的博客-CSDN博客

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注