【洛谷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

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c