题解 P2054 [AHOI2005]洗牌

洗牌???

吐槽一下题目的图片，差点误导了我

这么麻烦的题面当然先模拟啦。。。

打表发现每次洗牌后第 \(i\) 张牌会转移到第 \(2*i \%(n+1)\) 的位置上

即在\(\mod{n+1}\)意义下，\(i\) 和 \(2i\) 是同余的

so，可以列出一个同余方程：

\(i * 2^{m} \equiv l\pmod {n+1}\)

再转化为

\[2 ^ {m} * i + (n+1) * k = l\]

\[2^{m} * \frac{i}{l} + (n+1) * \frac{k}{l} = 1\]

此时利用\(exgcd\)完美地算出\(\frac{i}{l}\)，乘上\(l\)即可

注意：范围1e10，如果直接乘会gg，要用快速乘，和快速幂差不多

#include <cstdio>
#include <cctype>

using namespace std;

template<typename T> inline void read(T &x) {// 快读
    x = 0; T k = 1; char in = getchar();
    while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x *= k;
}

typedef long long ll;// 开long long

// 快速乘
inline ll mul(ll a, ll b, ll p) {
    // 将乘法变为加法，二进制优化，边加边模
    ll ans = 0;
    while (b) {
        if (b & 1)
            ans = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ans;
}

// 快速幂，其实只要写针对2的整次幂就行，这里犯懒。。。
inline ll q_pow(ll a, ll b, ll p) {
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = mul(ans, a, p) % p;
        a = mul(a, a, p) % p, b >>= 1;
    }
    return ans;
}

// 标配扩欧
void exgcd(ll a, ll b, ll &x, ll &y, ll &g) {
    if (!b)
        x = 1, y = 0, g = a;
    else {
        exgcd(b, a%b, y, x, g);
        y -= a / b * x;
    }
}

int main() {
    ll n, m, l, x, y, g, t;
    read(n), read(m), read(l);
    t = q_pow(2, m, n+1);// 2的m次幂
    exgcd(t, n+1, x, y, g);
    x = (x % (n+1) + n+1) % (n+1);// 注意exgcd后解可能为负
    printf("%lld\n", mul(x, l, n+1));// 乘上l
    return 0;
}