BZOJ1965: [Ahoi2005]SHUFFLE 洗牌(exgcd 找规律)
2024-08-29 14:09:54
Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 989 Solved: 660
[Submit][Status][Discuss]
Description
为了表彰小联为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张扑克牌的牌面大小是多少的科学家得胜。小联想赢取游戏的胜利,你能帮助他吗?
Input
有三个用空格间隔的整数,分别表示N,M,L (其中0< N ≤ 10 ^ 10 ,0 ≤ M ≤ 10^ 10,且N为偶数)。
Output
单行输出指定的扑克牌的牌面大小。
Sample Input
6 2 3
Sample Output
6
HINT
Source
非常巧妙的一道题、
通过找规律不难发现,第$i$个位置下一轮的位置为$2i \pmod {n + 1}$
那么下$m$轮的位置为$2^m i \pmod {n + 1}$
我们需要找到一个位置$x$,使得$2^m x \equiv L \pmod {n + 1}$
那么$x \equiv L * 2^{-x} \pmod {n + 1}$
做完了。。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<iostream>
#define int long long
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int x, y, N, M, L, mod;
int fastpow(int a, int p) {
int base = ;
while(p) {
if(p & ) base = (base * a) % mod;
a = (a * a) % mod; p >>= ;
}
return base % mod;
}
int exgcd(int a, int b, int &x, int &y) {
if(b == ) {x =; y = ; return a;}
int r = exgcd(b, a % b, x, y);
int t = x; x = y; y = t -(a / b) * y;
return r;
}
int inv(int a, int b) {
exgcd(a, b, x, y);
while(x < ) x += b;
return x % b;
}
main() {
N = read(); M = read(); L = read();
mod = N + ;
printf("%lld", L % mod * inv(fastpow(, M), mod) % mod);
}
最新文章
- __definedGetter\Setter__的一些想法
- 深度学习(dropout)
- 实例之HTML标签属性
- win server2008R2安装framework1.1后,在应用池中不能编辑选择framework1.1的解决办法
- REDIS key notification
- ZOJ Problem Set - 1025解题报告
- html_web存储
- Linux文件系统,ntfs分区显示只读文件系统,提示超级快损坏
- 201521123035《Java程序设计》第十四周学习总结
- .NET Core版本七牛云SDK使用
- 如何从零开始学习区块链技术——推荐从以太坊开发DApp开始
- 每天一点Linux系列之—vim
- 启动欢迎页面时,Android Studio设置全屏Activity
- 【python接口自动化框架-unittest】如何传参数到下一个case
- Swift中String与NSDate的互相转换
- C#:注册组件 (cmd)
- USB学习笔记连载(二十一):CY7C68013A进行数据传输(一)
- Linux软件源书写格式解析及本地yum源制作
- npm install ";Unexpected end of JSON input while parsing near";问题
- CImg、libjpeg--介绍、配置(操作JPEG)
热门文章
- (转) tcpdump参数解析及使用详解
- 树莓派ssh报错:WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED解决
- the wait queue
- Controller的使用
- C#开发短信的方法和简介(转)
- jquery的on()方法总结
- spring笔记3-AOP
- 【工作中学习】CreateProcessAsUser失败,错误码:1314
- 如何提升SharePoint 2010的性能
- Html + JS : 点击对应的按钮,进行选择是隐藏还是显示(用户回复功能)