P10797 题解

Register_int · 2024-07-21 16:19:19 · 题解

由于只能加 y 进制表示下的最高位，这个最高位显然是 \le x 的。这个最大值可以取到，当 y=x 时，x 的 y 进制表示是 10，直接加成 20 即可。每次操作会将 x 变成 2x，所以最终答案是 2^nx……
吗？事实上，当 x\le2 时这样是行不通的，因为没有 1 进制，2 进制下 20 会进位。所以单独讨论第一步：

那就做完了。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int mod = 1e9 + 7;

inline 
int qpow(int b, int p) {
    int res = 1;
    for (; p; p >>= 1, b = (ll)b * b % mod) if (p & 1) res = (ll)res * b % mod;
    return res;
}

int T, x, n;

int main() {
    for (scanf("%d", &T); T--;) {
        scanf("%d%d", &x, &n);
        if (x == 1) x = 2, n--;
        if (!n) { printf("%d\n", x); continue; }
        if (x == 2) x = 3, n--;
        printf("%d\n", (ll)x * qpow(2, n) % mod);
    }
}