【洛谷P2054洗牌】AC代码(扩展欧几里得+二分快速幂+二分龟速乘)

2024-06-20 20:18

本文主要是介绍【洛谷P2054洗牌】AC代码(扩展欧几里得+二分快速幂+二分龟速乘),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

题目链接
为了表彰小联为Samuel星球的探险所做出的贡献,小联被邀请参加Samuel星球近距离载人探险活动。

由于Samuel星球相当遥远,科学家们要在飞船中度过相当长的一段时间,小联提议用扑克牌打发长途旅行中的无聊时间。玩了几局之后,大家觉得单纯玩扑克牌对于像他们这样的高智商人才来说太简单了。有人提出了扑克牌的一种新的玩法。

对于扑克牌的一次洗牌是这样定义的,将一叠N(N为偶数)张扑克牌平均分成上下两叠,取下面一叠的第一张作为新的一叠的第一张,然后取上面一叠的第一张作为新的一叠的第二张,再取下面一叠的第二张作为新的一叠的第三张……如此交替直到所有的牌取完。

如果对一叠6张的扑克牌1 2 3 4 5 6,进行一次洗牌的过程如下图所示:

从图中可以看出经过一次洗牌,序列1 2 3 4 5 6变为4 1 5 2 6 3。当然,再对得到的序列进行一次洗牌,又会变为2 4 6 1 3 5。

游戏是这样的,如果给定长度为N的一叠扑克牌,并且牌面大小从1开始连续增加到N(不考虑花色),对这样的一叠扑克牌,进行M次洗牌。最先说出经过洗牌后的扑克牌序列中第L张扑克牌的牌面大小是多少的科学家得胜。小联想赢取游戏的胜利,你能帮助他吗?

输入格式

输入文件中有三个用空格间隔的整数,分别表示N,M,L(其中0<N≤10^10 ,0 ≤M≤10^10,且N为偶数)。

输出格式

单行输出指定的扑克牌的牌面大小。

输入输出样例

  • 输入 #1
6 2 3
  • 输出 #1
6
  • 说明/提示
0<N≤10^100≤M≤10^10,且N为偶数

前置知识

扩展欧几里得算法

贝祖定理

  • 若有整数a,b,c,在方程 a x + b y = c ax+by=c ax+by=c中,未知数x,y有整数解当且仅当c是gcd(a,b)的倍数,其中gcd(a,b)表示a,b的最大公因数。

欧几里得算法

  • gcd(a,b)=gcd(b,a%b)=…=gcd(d,0)=d

算法模板

int gcd(int a,int b){if(b==0) return a;else return gcd(b,a%b);
}

扩展欧几里得算法

  • 用于求解 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)

算法思想
按照欧几里得算法展开方程 a x + b y = g c d ( a , b ) = g c d ( b , a % b ) = b x ′ + ( a % b ) y ′ = . . . = 1 d + 0 y = g c d ( a , b ) ax+by=gcd(a,b)=gcd(b,a\%b)=bx'+(a\%b)y'=...=1d+0y=gcd(a,b) ax+by=gcd(a,b)=gcd(b,a%b)=bx+(a%b)y=...=1d+0y=gcd(a,b)
其中 b x ′ + ( a % b ) y ′ = b x ′ + ( a − a / b ∗ b ) y ′ = a y ′ + ( x ′ − a / b ∗ y ′ ) b = a x + b y bx'+(a\%b)y'=bx'+(a-a/b*b)y'=ay'+(x'-a/b*y')b=ax+by bx+(a%b)y=bx+(aa/bb)y=ay+(xa/by)b=ax+by
x = x ′ , y = x ′ − a / b ∗ y ′ x=x',y=x'-a/b*y' x=x,y=xa/by
最终 g c d ( a , b ) x 0 + 0 y 0 = g c d ( a , b ) gcd(a,b)x_0+0y_0=gcd(a,b) gcd(a,b)x0+0y0=gcd(a,b),即 x 0 = 1 , y 0 ∈ R x_0=1,y_0\in R x0=1,y0R,所求得 x , y x,y x,y只是一组特解,通解为 ( x + k ∗ b / d , y − k ∗ b / d ) (x+k*b/d,y-k*b/d) (x+kb/d,ykb/d),推导方法略

算法模板

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;//gcd(a,b)x=gcd(a,b)y=0;//y随意return a;}ll gcd=exged(b,a%b,x,y),r;r=x;x=y;//x=y'y=r-a/b*y;//y=x'-a/b*y'return gcd;
}

用途

  1. 求乘法逆元
  2. 求解 a x + b y = c ax+by=c ax+by=c
  3. 求同余方程

乘法单位元:任何数乘以单位元等于这个数,显然乘法的单位元是1。
乘法逆元:任何数乘以他的乘法逆元等于单位元,比如2*0.5=1,0.5就是1的乘法逆元,但这不是我们需要的东西,我们需要的是在模运算下的整数乘法逆元。

二分快速幂与二分龟速乘

二分快速幂

二分幂
  • 二分幂,就是平常所用的幂运算化简方法,一般采用递归实现,不建议使用


a b = { a ∗ ( a 2 ) b 2 , b 为奇数 ( a 2 ) b 2 , b 为偶数 a^b=\left\{ \begin{array}{l} a*\left( a^2 \right) ^{\frac{b}{2}},b\text{为奇数}\\ \left( a^2 \right) ^{\frac{b}{2}},b\text{为偶数}\\ \end{array} \right. ab={a(a2)2b,b为奇数(a2)2b,b为偶数
转化为递归方程为
f ( a , b ) = { 1 , b = 0 a ∗ f ( a 2 , b 2 ) , b 为奇数 f ( a 2 , b 2 ) , b 为偶数 f\left( a,b \right) =\left\{ \begin{array}{l} 1,b=0\\ a*f\left( a^2,\frac{b}{2} \right) ,b\text{为奇数}\\ f\left( a^2,\frac{b}{2} \right) ,b\text{为偶数}\\ \end{array} \right. f(a,b)=1,b=0af(a2,2b),b为奇数f(a2,2b),b为偶数
算法模板

typedef long long ll;
ll efm(ll a,ll b,ll n){if(b==0) return 1;if(b&1) return a*efm(a*a%n,b>>1,n);else return efm(a*a%n,b>>1,n);
}
快速幂
  • 采用二分的思想利用二进制快速求解 a b a^b ab

算法思想
这里用b表示二进制数,
3 13 = 3 b 1101 = 3 1 ∗ b 1000 ∗ 3 1 ∗ b 100 ∗ 3 0 ∗ b 10 ∗ 3 1 ∗ b 1 3^{13}=3^{b1101}=3^{1*b1000}*3^{1*b100}*3^{0*b10}*3^{1*b1} 313=3b1101=31b100031b10030b1031b1
3 b 10 = ( 3 b 1 ) 2 3^{b10}=(3^{b1})^2 3b10=(3b1)2
3 b 100 = ( 3 b 10 ) 2 3^{b100}=(3^{b10})^2 3b100=(3b10)2
3 b 1000 = ( 3 b 100 ) 2 3^{b1000}=(3^{b100})^2 3b1000=(3b100)2
可以看出,每一项都是前一项的平方,原本需要计算13次的算法被优化到了计算4次,本算法时间复杂度是 O ( l o g 2 b ) O(log_2b) O(log2b)

算法模板

  • 通常,本算法的幂非常大,所求结果常需要取模
typedef long long ll;
ll ksm(ll a,ll b,ll n){//a^b%nll ret=1;//累乘结果计算while(b>0){//非0次幂则计算if(b&1){//判断最低为是否为1,0不需要乘入ret=ret*a%n;}a=a*a%n;//由上述推导可得平方关系b>>=1;//b右移一位}return ret;
}

二分龟速乘

  • 对于快速幂算法的改进

二分快速幂算法存在的问题
在使用二分快速幂计算乘法时,尽管采用了%n来防止溢出,但仍然会有溢出现象,因为x*x%n,在x*x时就有可能溢出。

二分乘
  • 其实就是龟速乘的二分版本,一般用递归实现,不建议使用

乘法可以写成累加的形式,诸如
3 ∗ 5 = 3 + 3 ∗ 4 = 3 + ( 2 ∗ 3 ) ∗ 2 = 3 + 6 ∗ 2 = 3 + 12 3*5=3+3*4=3+(2*3)*2=3+6*2=3+12 35=3+34=3+(23)2=3+62=3+12
转化为递归方程为
f ( a , b ) = { 0 , b = 0 a + f ( 2 a , b 2 ) , b 为奇数 f ( 2 a , b 2 ) , b 为偶数 f\left( a,b \right) =\left\{ \begin{array}{l} 0,b=0\\ a+f\left( 2a,\frac{b}{2} \right) ,b\text{为奇数}\\ f\left( 2a,\frac{b}{2} \right) ,b\text{为偶数}\\ \end{array} \right. f(a,b)=0,b=0a+f(2a,2b),b为奇数f(2a,2b),b为偶数
算法模板

typedef long long ll;
ll gsc(ll a,ll b,ll n){if(b==0) return 0;if(b&1) return (a+gsc((a<<1)%n,b>>1))%n;else return gsc((a<<1)%n,b>>1)%n;
}
龟速乘

我们可以让x*y也变成类似于快速幂的运算形式,诸如
3 ∗ 5 = 3 ∗ b 101 = 3 ∗ ( 1 ∗ b 1 + 0 ∗ b 10 + 1 ∗ b 100 ) 3*5=3*b101=3*(1*b1+0*b10+1*b100) 35=3b101=3(1b1+0b10+1b100)
= 1 ∗ 3 ∗ b 1 + 0 ∗ 3 ∗ b 10 + 1 ∗ 3 ∗ b 100 =1*3*b1+0*3*b10+1*3*b100 =13b1+03b10+13b100
其中
3 ∗ b 10 = 3 ∗ b 1 + 3 ∗ b 1 3*b10=3*b1+3*b1 3b10=3b1+3b1
3 ∗ b 100 = 3 ∗ b 10 + 3 ∗ b 10 3*b100=3*b10+3*b10 3b100=3b10+3b10
不难发现,每一项都是前一项的二倍,由于本算法甚至慢于for循环相加,故得名龟速乘,时间复杂度为 O ( l o g 2 b ) O(log_2b) O(log2b)

算法模板

typedef long long ll;
ll gsc(ll a,ll b,ll n){ll ret=0;//累加结果计算while(b>0){//非0乘则计算if(b&1){//判断最低为是否为1,0不需要加入ret=(ret+a)%n;}a=(a+a)%n;//由上述推导可得平方关系b>>=1;//b右移一位}return ret;
}

快速幂的改进

  • 引入了龟速乘后,我们便可以改进快速幂算法
typedef long long ll;
ll ksm(ll a,ll b,ll n){ll ret=1;while(b>0){if(b&1){ret=gsc(ret,a,n);//修改位}a=gsc(a,a,n);//修改位b>>=1;}return ret;
}

题解

根据题目不难看出在 n n n张牌中第 x x x张牌经过 m m m伦洗牌后与所在位置 l l l满足:
x ∗ 2 m = l ( m o d n + 1 ) x*2^m=l(mod\ n+1) x2m=l(mod n+1)
两种解法:

  1. 通过同余方程求逆元解答
  2. 直接求同余方程解

由于本文旨在学习更多的知识,采用逆元解法
这是线性同余方程,需要快速幂结合扩展欧几里得算法求解。
由于 a x = b ( m o d n ) ax=b(mod\ n) ax=b(mod n),令 d = g c d ( a , n ) , t = n / d d=gcd(a,n),t=n/d d=gcd(a,n),t=n/d,则 x x x的最小正整数解为 x = ( x % t + t ) % t x=(x\%t+t)\%t x=(x%t+t)%t,在本题中 a a a为偶数, n + 1 n+1 n+1为奇数,则 t = n t=n t=n

快速幂+龟速乘代码

#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,l,x,y;
ll gsc(ll x,ll m){ll ret=0;while(m){if(m&1) ret=(ret+x)%n;x=(x+x)%n;m>>=1;}return ret;
}
ll ksm(ll x,ll m){ll ret=1;while(m){if(m&1) ret=gsc(ret,x);x=gsc(x,x);m>>=1;}return ret;
}
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll r=exgcd(b,a%b,x,y);ll c=x;x=y;y=c-a/b*y;return r;
}
int main(){scanf("%lld%lld%lld",&n,&m,&l);n++;ll k=ksm(2,m);exgcd(k,n,x,y);x=gsc(l,x%n+n);printf("%lld",x%n);return 0;
}

二分幂+二分乘代码

#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,l,x,y;
ll efc(ll x,ll m){if(m==0) return 0;if(m&1) return (x+efc((x<<1)%n,m>>1))%n;else return efc((x<<1)%n,m>>1)%n;
}
ll efm(ll x,ll m){if(m==0) return 1;if(m&1) return efc(x,efm(efc(x,x)%n,m>>1));else return efm(efc(x,x)%n,m>>1);
}
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll r=exgcd(b,a%b,x,y);ll c=x;x=y;y=c-a/b*y;return r;
}
int main(){scanf("%lld%lld%lld",&n,&m,&l);n++;ll k=efm(2,m);exgcd(k,n,x,y);x=efc(l,x%n+n);printf("%lld",x%n);return 0;
}

扩展

快速乘

  • 经Cyan_rose介绍,《论程序底层优化的一些方法与技巧》这篇论文中提到了快速乘

  • 可以按此代码实现快速乘
cin>>a>>b>>mod;
cout<<((a*b-(long long)((long double)a*b/mod)*mod+mod)%mod);

这篇关于【洛谷P2054洗牌】AC代码(扩展欧几里得+二分快速幂+二分龟速乘)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1079147

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论