【BZOJ1965】[AHOI2005] SHUFFLE 洗牌（数学题）

点此看题面

大致题意： 有一叠扑克牌编号为$1\sim n$（$n$为偶数），每次洗牌将扑克牌平均分成上下两叠，取下面一叠的第一张作为新的一叠的第一张，然后取上面一叠的第一张作为新的一叠的第二张，再取下面一叠的第二张作为新的一叠的第三张……如此交替直到所有的牌取完。问$m$次洗牌后第$l$张扑克牌的编号。

数学题

$n,m$这么大，比较显然是一道数学题。

设当前位置为$x$，则不难发现，每次洗牌之后，下一次的位置为：$2x$%$(n+1)$

以此类推，经过$m$次洗牌，这张扑克牌的位置应为$2^mx$%$(n+1)$

既然这样，题目要我们求的就出一个$x$满足$$2^mx\equiv l(mod\text{ }n+1)$$

根据等式的性质，原式可化为$$x\equiv l·(2^m){-1}(mod\text{ }n+1)$$

因此，我们只需求出$2^m$在模$n+1$意义下的乘法逆元，再乘以$l$，就可以求出$x$了。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define uint unsigned int

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define abs(x) ((x)<0?-(x):(x))

#define Fsize 100000

#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)

#define pc(ch) (putchar(ch))

int OutputTop=0;char Fin[Fsize],*FinNow=Fin,*FinEnd=Fin,OutputStack[Fsize];

using namespace std;

LL n,m,l;

inline void read(LL &x)

{

    x=0;static char ch;

    while(!isdigit(ch=tc()));

    while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));

}

inline void write(LL x)

{

    if(!x) return (void)pc('0');

    while(x) OutputStack[++OutputTop]=x%10+48,x/=10;

    while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;

}

inline LL quick_pow(LL x,LL y,LL MOD)//快速幂

{

    register LL res;

    for(res=1;y;(x*=x)%=MOD,y>>=1) if(y&1) (res*=x)%=MOD;

    return res;

}

inline void exgcd(LL x,LL y,LL &s1,LL &s2)//exgcd求逆元

{

    if(!y) return (void)(s1=1,s2=0);

    exgcd(y,x%y,s2,s1),s2-=x/y*s1;

}

inline LL Inv(LL x,LL y)//求逆元

{

    register LL s1,s2;

    exgcd(x,y,s1,s2);

    return (s1%y+y)%y;

}

int main()

{

    return read(n),read(m),read(l),write(Inv(quick_pow(2,m,n+1),n+1)*l%(n+1)),0;//求出2^m在模n+1意义下的逆元乘以l模n+1后的值

}

巴特西

【BZOJ1965】[AHOI2005] SHUFFLE 洗牌（数学题）

数学题

代码

最新文章

热门文章