卡片

时间限制: 1 Sec 内存限制: 128 MB

题目描述

你有一叠标号为1到n的卡片。
你有一种操作，可以重排列这些卡片，操作如下：
1.将卡片分为前半部分和后半部分。
2.依次从后半部分，前半部分中各取一张卡片，放到新的序列中。
例如，对卡片序列(1,2,3,4,5,6)操作后的结果为(4,1,5,2,6,3)。
现在你有一个初始为(1,2,3,⋯,n)的卡片序列，你需要求出进行m次操作之后第x个位置上的卡片的标号。

输入

第一行包含三个非负整数n,m,x。

输出

输出一行一个数，表示答案。

样例输入

6 2 3

样例输出

提示

对于60%的数据，m≤10⁷。
对于100%的数据，0≤n,m,x≤10⁹。
数据有梯度，保证n为偶数。

题解：

假设原始位置为x（同时也是数值），当前位置为p；

因为变换一次后，位置要么变为2x，要么变为2x-(n+1)，所以有等式(2^m)*x+(n+1)*y=p；

由于我们只需要求出x，所以等式可以写成((2^m)%(n+1))*x+(n+1)*y=p；

简单理解一下extend_gcd函数的执行过程就可以得到以上结论。

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll qpow(ll a,ll b,ll mod)
 5 {
 6     ll res=1;
 7     while(b){
 8         if(b&1) res=res*a%mod;
 9         a=a*a%mod;
10         b>>=1;
11     }
12     return res;
13 }
14 ll extend_gcd(ll a,ll b,ll &x,ll &y)
15 {
16     if(b==0){
17         x=1;y=0;
18         return a;
19     }
20     ll r=extend_gcd(b,a%b,y,x);
21     y-=x*(a/b);
22     return r;
23 }
24 int main()
25 {
26     ll n,m,p,a,b,x,y;
27     scanf("%lld %lld %lld",&n,&m,&p);
28     a=qpow(2,m,n+1);b=n+1;
29     ll gcd=extend_gcd(a,b,x,y);
30     b/=gcd;p/=gcd;
31     x=x%b*p%b;
32     if(x<0) x+=b;
33     printf("%lld
",x);
34     return 0;
35 }

View Code