这个题涉及到了一些线段树复杂度的计算的东西,你如果看懂了这个也就会做这个题了。
大致是:
表示一个节点,代表的区间长度是,询问的区间是否贴合了这个节点的左端点/右端点,在内部一共被涉及到了个节点的方案数。
然后分类讨论即可。
容易注意到其实最多只会询问到种长度,所以离散化一下就可以了。
#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
#define ls ((n>>1)+(n&1))
#define rs (n>>1)
#define mod 998244353
using namespace std;
int n,k;
map<int,ll> dp[125][2][2]; //一共这么多个点,选多少个点,是否贴了左/右边界
ll get(int n,int c,int l,int r)
{
if (c<=0) return 0;
if (dp[c][l][r].count(n)) return dp[c][l][r][n];
// cout<<n<<" "<<c<<" "<<l<<" "<<r<<endl;
if (l==1 && r==1) //如果两边都靠上了则特判
{
if (c==1) return dp[c][l][r][n]=1;
else return dp[c][l][r][n]=0;
}
if (n==1) //如果只剩一个点了,就直接特判一下
{
return dp[c][l][r][n]=0;
}
ll ret=0;
if (l==0 && r==0) //两边都不贴边界
{
//case1:递归一个(0,0)
ret+=get(ls,c-1,0,0)+get(rs,c-1,0,0);
//case2:左边递归(0,1)或者右边递归(1,0)
ret+=get(ls,c-1,0,1)+get(rs,c-1,1,0);
//case3:左边递归(0,1)同时右边递归(1,0)
//根节点用1个,左边lef个,右边c-1-lef个
for (int lef=1;lef<c;lef++)
{
ret+=get(ls,lef,0,1)*get(rs,c-1-lef,1,0);
}
}
if (l==0 && r==1) //贴右边界
{
//case1:彻底在右子树,要么(1,1)要么(0,1)
ret+=get(rs,c-1,1,1)+get(rs,c-1,0,1);
//case2:右子树全在,左子树(0,1)
ret+=get(rs,1,1,1)*get(ls,c-2,0,1);
}
if (l==1 && r==0) //贴左边界
{
//case1:彻底在左子树
ret+=get(ls,c-1,1,1)+get(ls,c-1,1,0);
//case2:左子树全在,右子树(1,0)
ret+=get(ls,1,1,1)*get(rs,c-2,1,0);
}
return dp[c][l][r][n]=ret;
}
int main()
{
cin>>n>>k;
for (int i=1;i<=k;i++)
cout<<get(n,i,0,0)+get(n,i,0,1)+get(n,i,1,0)+get(n,i,1,1)<<" ";
}