P9915

cosf · 2023-12-09 22:03:33 · 题解

P9915

观察性质题。

我们打一个 n=5 的表。为了不影响阅读，图片放到了文末。

可以发现，每一个连通块都有如下性质：

1. 形如一个（倒）金字塔。
2. 其中一个角是所谓的“直角”。
3. 从横着来看，除了最宽的那一层，同宽度的层的层数等于该宽度减一的层数除以 2。

那么，我们可以推出底部宽为 k 的金字塔的大小：

至此，这道题已经解决了一半。

现在，我们要求的是 (x, y) 所在的金字塔的底边大小。

可以发现，假设 x 的二进制如下，有两种情况：

对于情况 (1)，观察表可以发现，存在 y' 使得 x_y = x_{y+1} = \dots = x_{y'} = 1, x_{y' + 1} = 0（此处 x_y 表示 x 在二进制下的第 y 位，从第 0 位开始记），则该金字塔的底部宽为 y' + 1。

对于情况 (2)，同样可得，若存在 y' 使得 x_y = x_{y + 1} = \dots = x_{y'} = 0, x_{y' = 1} = 1，则该金字塔的底部宽为 y' + 1，否则为 n。

注意，当 y \ge 64 时，x_y 是绝对不可能为 1 的，需优化此情况。

关于实现，计算 x_y 时一定要用 1ll 去左移而不是 1。我因此罚了好几发。

代码

#include <iostream>
using namespace std;

#define MOD 998244353

using ll = unsigned long long;

ll po(ll b, ll p)
{
    ll r = 1;
    while (p)
    {
        if (p & 1)
        {
            r = r * b % MOD;
        }
        b = b * b % MOD;
        p >>= 1;
    }
    return r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    int q;
    cin >> n >> q;
    while (q--)
    {
        ll x, y;
        cin >> x >> y;
        if (y >= 64)
        {
            cout << (po(2, n) - 1 + MOD) % MOD << endl;
            continue;
        }
        if (x & (1ll << y))
        {
            while (x & (1ll << y) && y < n)
            {
                y++;
            }
            cout << (po(2, y) - 1 + MOD) % MOD << endl;
        }
        else
        {
            while (!(x & (1ll << y)) && y < n)
            {
                y++;
            }
            cout << (po(2, y) - 1 + MOD) % MOD << endl;
        }
    }
    return 0;
}

附