AtCoder Beginner Contest 321

SuntoryProgrammingContest2023（AtCoder Beginner Contest 321）

E - Complete Binary Tree

有 $T$ 组询问，每组询问 $(N,X,K)$，询问在一棵有 $N$ 个节点的二叉树上离节点 $X$ 距离为 $K$ 的节点数量。

距离节点 $X$ 为 $K$ 的点可以是：从 $X$ 往下走 $K$ 步；往上走一步，再从另一棵子树往下走 $K-1$ 步；依此类推。对于节点 $i$，向下走 $K$ 步到达的节点为 $[i\times2^K,(i+1)\times2^{K})$。所以直接枚举即可，每次回答是 $\log$ 级别的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int depth(ll x)
{
    int res=0;
    while(x>1)
    {
        x>>=1;
        res++;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        ll n,x,k;cin>>n>>x>>k;
        int dn=depth(n),dx=depth(x);
        ll ans=0;
        for(int i=0;i<=dx;i++)
        {
            if(dx-i>k) continue;
            if(i+k-(dx-i)>dn) continue;
            ll l,r;
            if(i==dx)
                l=x<<k,r=(x+1)<<k;
            else if(dx-i==k)
                l=x>>k,r=(x>>k)+1;
            else
            {
                ll z=x>>(dx-i);
                l=z*2+(~x>>(dx-i-1)&1);
                l<<=(k-(dx-i)-1);
                r=l+(1LL<<(k-(dx-i)-1));                
            }
            if(l>n) continue;
            r=min(r,n+1);
            ans+=r-l;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

G - Electric Circuit

有 $n$ 个点，另有两个长度为 $m$ 值域为 $n$ 的序列 $a,b$，随机排列后将 $a_i,b_i$ 相连，求连通块个数的期望。

$n$ 的范围让人想到状压。枚举由 $n$ 个点构成的子集，计算它们恰好形成一个连通块的概率，然后相加就是答案。

记当前枚举的集合为 $s$，要求它恰好形成一个连通块的方案，可以考虑容斥：枚举每一个真子集 $t$，当它形成一个连通块时，再加上剩下的点，连通块数量一定超过一个，所以这些都是不合法的方案。为了避免重复，可以钦定最小的点一定包含在 $t$ 内。

#include <bits/stdc++.h>
using namespace std;
const int p=998244353;
const int N=1e5+5;
typedef long long ll;
int r[1<<17],b[1<<17],rcnt[17],bcnt[17];
ll fac[N],f[1<<17];
int lowbit(int x){return x&-x;}
ll fpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fac[0]=1;
    for(int i=1;i<N;i++) fac[i]=i*fac[i-1]%p;
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++) 
    {
        int x;cin>>x;
        rcnt[--x]++;
    }
    for(int i=1;i<=m;i++) 
    {
        int x;cin>>x;
        bcnt[--x]++;
    }
    int maxs=1<<n;
    ll ans=0;
    for(int s=1;s<maxs;s++)
    {
        for(int i=0;i<n;i++)
            if((s>>i)&1)
                r[s]+=rcnt[i],b[s]+=bcnt[i];
        if(r[s]!=b[s]) continue;
        f[s]=fac[r[s]];
        for(int t=s&(s-1);t;t=(t-1)&s)
        {
            if(lowbit(t)!=lowbit(s)||r[t]!=b[t]) continue;
            f[s]=(f[s]-f[t]*fac[r[s]-r[t]]%p+p)%p;
        }
        ans=(ans+f[s]*fac[m-r[s]])%p;
    }
    cout<<ans*fpow(fac[m],p-2)%p<<'\n';
    return 0;
}