lulaalu

字数

400 字

阅读时间

3 分钟

原题：洗牌

题意

偶数的 $n$ ，初始序列 $[1, 2, 3, \dots, n]$ ，取前一半和后一半再交替放置

即 $[1, 2, 3, 4, 5, 6, 7, 8]$ 取 $[1, 2, 3, 4]$ $[5, 6, 7, 8]$

后半部分先放，变成 $[5, 1, 6, 2, 7, 3, 8, 4]$

给 $n$ 、交换次数 $m$ 、 $l$

要求求出洗完后的第 $l$ 张扑克的数值

思路

手玩发现，当前扑克的位置 $i$ 经过洗牌后会变成 $2 * i % (n + 1)$

经过 $m$ 次洗牌就是 $i * 2^{m} % (n + 1) = l$ 要求 $i$

通过[[扩展欧几里得]]的知识可以将上式转化为 $i * 2^{m} + k (n + 1) = l$

类似于形式 $a x + b y = c$

由于 $2^{m}$ 和 $n + 1$ 的[[../../../数据结构与算法/数学/GCD]]一定是1

所以当求出 $x 2^{m} + y (n + 1) = 1$ 的一个特解 $(x_{0}, y_{0})$ 后， $l x_{0}$ 就是答案

代码

由于范围问题，需要用int128，或者位运算乘法

CPP

#define i128 __int128_t
i128 d, x, y, px, py;
i128 n, m, l;

void exgcd(i128 a, i128 b) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        exgcd(b, a % b);
        px = x;
        py = y;
        x = py;
        y = px - (a / b) * py;
    }
}

i128 ksm(i128 a, i128 b, i128 p) {
    i128 res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void print(i128 a, string s = "") {
    string anss = "";
    while (a) {
        anss += a % 10 + '0';
        a /= 10;
    }
    if (anss == "") anss = "0";
    reverse(all(anss));
    cout << anss << s;
}

signed main() {
    IOS;
    int nn, mm, ll;
    cin >> nn >> mm >> ll;
    n = nn;
    m = mm;
    l = ll;

    i128 a = ksm(2, m, n + 1);
    exgcd(a, n + 1);
    x = (x % (n + 1) + (n + 1)) % (n + 1);
    i128 ans = (x * l) % (n + 1);

    print(ans);
    return 0;
}

贡献者

lulaalu

文件历史

最后编辑于 22 天前查看完整历史

题意 ​

思路 ​

代码 ​

贡献者 ​

文件历史 ​

题意

思路

代码

贡献者

文件历史