AT220E

题目传送门

思路

对于两点的位置关系分两种情况讨论。

当前点为。

①为点，往下走到达点，显然这个点的贡献就是。

②下面是两个点，设左子树的路径长度为 l ，那么右子树的长度为 d−l，因为长度的分配，有种，因为这两条路径是固定的，所有剩下种方案。

代码

#include
using namespace std;
long long n,d,p[2000001],s,l,r,i;
const int P=998244353;
signed main(){
	cin>>n>>d;
	p[0]=1;
	for(i=1;i<=2e6;++i)
		p[i]=p[i-1]*2%P;
	for(i=1;i<=n;++i){
		if(n-i>=d)
			s=(s+p[d]*p[i-1]%P)%P;
		l=min(n-i,d-1);
		r=d-l;
		if(r<=n-i)
			s=(s+(l-r+1)*p[d-2]%P*p[i-1]%P)%P; 
	}
	cout<