P2054 [AHOI2005]洗牌

说在前面

别问，问就是暴力+循环节+O2可以过。

啊，正解是啥？
发现对于每次洗牌，原来在第(x)张的牌都翻到了(2x mod(n + 1))。所以，对于第(x)张牌，在经过(m)次洗牌后，变成(x cdot 2^m mod (n + 1))。而最后落在第(L)张的那个，可以列同余方程：

[x cdot 2 ^ m equiv L pmod{n + 1} ]

变形，得

[x equiv L (2^m)^{-1} pmod{n + 1} ]

用exgcd求出(2^m)在(pmod{n + 1})下的逆元后乘上(L)即为所求。

# include <bits/stdc++.h>
using namespace std;

long long n,m,L;

void exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b == 0)
    {
        x = 1,y = 0;
        return;
    }
    exgcd(b,a % b,x,y);
    long long z = x;
    x = y,y = z - (long long)(a / b) * y;
    return;
}

long long mul(long long x,long long y)
{
    long long ans = 0;
    while(y)
    {
        if(y & 1) ans = (ans + x) % (n + 1);
        y >>= 1;
        x = (x + x ) % (n + 1);
    }
    return ans % (n + 1);
}

long long ksm(long long x,long long p)
{
    x %= (n + 1);
    long long ans = 1;
    while(p)
    {
        if(p & 1) ans = mul(ans,x) % (n + 1);
        p >>= 1;
        x = mul(x,x) % (n + 1);
    }
    return ans % (n + 1);
}

int main(void)
{
    scanf("%lld%lld%lld",&n,&m,&L);
    long long x = 0,y = 0;
    exgcd(ksm(2,m),n + 1,x,y);
    if(x < 0) x += (ceil(double(abs(x)) / double(n + 1))) * (n + 1);
    x %= (n + 1);
    printf("%lld
",mul(x,L) % (n + 1));
    return 0;
}