#C231106A. 点分治(tree)

标签（Label）

• 二进制
• 观察+分析
• 数学推理

网址

题目详情 - 点分治(tree) - Super

题解 - 点分治(tree) - Super

题解

观察可得：

• 性质1：将题目给的图转换成二进制，容易观察得：若末尾有 $w$ 个 $0$ , 要求的距离为 $d$ , 易得该点儿子的方案数为：$ways = C_{w}^k$ ， 其中记得特判 $k>w,k=w,k=0,k<0$ 的情况。

• 性质2：当前点到其根节点的距离为 $\verb!__popcount(x)!$ , 令人联想到了 $\verb!lowbit(x)!$ ，然而由于题目直接给了二进制数，该题就变得非常简单了。

非常容易推出：

​ $ans= \sum C_{v[i]}^{d-i} - C_{v[i-1]}^{d-i+1}$

由于方程式表答得情况数不够完整，因此给出核心代码：

int ans=C(v[0],d)%mod;
For(i,1,k){
	if(d-i-1<0) break;
	ans=(ans+C(v[i],d-i)-C(v[i-1],d-i-1)+mod)%mod;
}if(d<=k)ans=(ans+1)%mod;
cout<<(ans%mod+mod)%mod<<'\n';

注意开 $long long$ 以及求逆元。

代码

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int mod = 998244353;
const int N = 10123456;
int num[N]; 
int n,q;
int bas[N],inv[N];

inline int ksm(int x,int k){
	int res=1;while(k){
		if(k&1) res=res*x%mod;
		x=x*x%mod,k>>=1;
	}return res;
}

inline int C(int n,int m){
	if(m>n || m<0) return 0;
	if(m==0 || n==m) return 1;
	return bas[n]*inv[m]%mod*inv[n-m]%mod;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("tree");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n>>q;
	
	//求出1~n的逆元 
	bas[1]=1;For(i,2,n) bas[i]=bas[i-1]*i%mod;
	inv[n]=ksm(bas[n],mod-2);
	Rof(i,n-1,1) inv[i]=inv[i+1]*(i+1)%mod;
	
	while(q--){//O(q*klogk) 
		int k=input();
		For(i,0,k-1) num[i]=input();num[k]=n;
		sort(num,num+k+1);
		int d=input();
		
		int ans=C(num[0],d)%mod;
		For(i,1,k){
			if(d-i-1<0) break;
			ans=(ans+C(num[i],d-i)-C(num[i-1],d-i-1)+mod)%mod;
		}if(d<=k)ans=(ans+1)%mod;
		cout<<(ans%mod+mod)%mod<<'\n';
		
//		fill(num,num+k+1,0);
	}
	return 0;
}