P9915 「RiOI-03」3-2 考虑将表格逆时针旋转九十度。 首先易证得一个结论：对于一个点，竖直向上找到同颜色的，若它是从下往上数的第 kk 个（从 0 开始），那么连通块的大小就是 2k−12^k-1。 对于一个 x">2y>x2^y>x，要找的位置一定是 0，那么向上找一定是第 nn 层的 0，直接输出 2n−12^n-1 即可。 对于其余的 yy，因为这时满足 2y≤x2^y\le x，所以直接按照上述步骤模拟，复杂度没有问题。 代码： #include 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>y)&1)==((x>>(y+1))&1)) y++; printf("%lld\n",(qpow(2,y+1)+mod-1)%mod); } } return 0; } `#include 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+1log2(x)&&((x>>y)&1)==((x>>(y+1))&1)) y++; printf("%lld\n",(qpow(2,y+1)+mod-1)%mod); } } return 0; }`
P9915 「RiOI-03」3-2
笔记