P9915 「RiOI-03」3-2

用户头像 发布于 14 小时前 4 次阅读 OI

P9915 「RiOI-03」3-2

考虑将表格逆时针旋转九十度。

首先易证得一个结论：对于一个点，竖直向上找到同颜色的，若它是从下往上数的第 kk 个（从 0 开始），那么连通块的大小就是 2k−12^k-1。

对于一个 2y>x2^y>x，要找的位置一定是 0，那么向上找一定是第 nn 层的 0，直接输出 2n−12^n-1 即可。

对于其余的 yy，因为这时满足 2y≤x2^y\le x，所以直接按照上述步骤模拟，复杂度没有问题。

代码：

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

typedef long long ll;
const ll mod=998244353;
ll n,q;

ll qpow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

int main(){
    scanf("%lld%lld",&n,&q);
    while(q--){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        if(x==0||y>log2(x)) printf("%lld\n",(qpow(2,n)+mod-1)%mod);
        else{
            while(y+1<=log2(x)&&((x>>y)&1)==((x>>(y+1))&1)) y++;
            printf("%lld\n",(qpow(2,y+1)+mod-1)%mod);
        }
    }
    return 0;
}