题解：P17339 【MX-X30-T5】メタモリボン
lailai0916
·
·
题解
题意简述
把区间 [L,R] 内的数补成等长的 B 进制串。
任选若干字符串建立字典树，忽略边权与点编号，
求能得到多少棵本质不同的非空无标号有根树。
解题思路
把所有长度为 h 的 B 进制串按数值排序。
它们正好是满 B 叉字典树从左到右的 B^h 个叶子。
对一棵树而言，根的孩子没有顺序。
若每棵非空子树有 x 种形态，根有 k 个非空孩子，
那么孩子形态构成大小为 k 的多重集，方案数为：
M(x,k)=\binom{x+k-1}{k}
记 F_h 为高度为 h 的完整块能产生的非空树形数。
高度为 0 时只剩一个叶子，所以 F_0=1。
高度为 h 时，根可以保留 1 至 B 个孩子，故：
\begin{aligned}
F_0 & =1 \\
F_h & =\sum_{k=1}^{B}M(F_{h-1},k) \\
& =\binom{F_{h-1}+B}{B}-1
\end{aligned}
接着处理从最左侧开始的连续叶子。
记 P_h(n) 为高度为 h 的完整块中，
只允许使用前 n 个叶子时的树形数。
令 m=B^{h-1}，并写成：
n=qm+r
其中 0\le r<m。
前 q 个孩子对应完整块。
它们已经能产生根度数不超过 q 的全部多重集，数量为：
\binom{F_{h-1}+q}{q}-1
若 r=0，答案就是这一项。
否则还有一个前缀边界块，其中可用树形集合大小为 P_{h-1}(r)。
只有根度数恰为 q+1 时会产生新树形。
此时孩子多重集必须至少含有一种边界块可产生的形态，因此新增：
\binom{F_{h-1}+q}{q+1}
-\binom{F_{h-1}-P_{h-1}(r)+q}{q+1}
这便得到 P_h(n) 的递归计算。
长度较大的前缀包含长度较小的前缀，
所以它们能产生的树形集合也满足包含关系。
逐位执行 d\mapsto B-1-d，会把一个前缀翻转为等长后缀，
同时只置换每个节点的孩子，不改变无标号树形。
因此，等长前缀与后缀能产生完全相同的树形集合。
现在考虑一般区间。
若 L 与 R 的当前最高位相同，所有树的根都只有同一个孩子。
删去这一位后递归，树形数量不变。
在最高的不同位处，区间依次由左边界后缀、
设两个边界块的长度为 $x,y$，并记：
$$
\begin{aligned}
A & =P_{h-1}(x) \\
C & =P_{h-1}(y) \\
I & =P_{h-1}(\min(x,y)) \\
V & =A+C-I \\
U & =F_{h-1}
\end{aligned}
$$
两个边界树形集合分别有 $A,C$ 个元素。
由前缀集合的嵌套性，它们的交集大小为 $I$，并集大小为 $V$。
按最终根的度数分类。
根度数不超过 $q$ 时，完整块已经能产生所有方案，贡献为：
$$
G_0=\binom{U+q}{q}-1
$$
根度数为 $q+1$ 时，至少要使用一个边界块。
也就是多重集中至少出现一种并集内的形态，贡献为：
$$
G_1=\binom{U+q}{q+1}-\binom{U-V+q}{q+1}
$$
根度数为 $q+2$ 时，两个边界块都必须非空。
先容斥统计同时含有左、右边界形态的多重集：
$$
\begin{aligned}
G_2 & =\binom{U+q+1}{q+2} \\
& \mathrel{}-\binom{U-A+q+1}{q+2} \\
& \mathrel{}-\binom{U-C+q+1}{q+2} \\
& \mathrel{}+\binom{U-V+q+1}{q+2} \\
& \mathrel{}-I\binom{U-V+q}{q+1}
\end{aligned}
$$
容斥的前四项仍会多算一种情况：
多重集在并集中只有一个元素，且该元素属于交集。
同一个出现位置不能同时分配给两个边界块，
所以最后一项从 $I$ 种交集形态中任选一种，
再从并集外选择其余 $q+1$ 个元素，将这些非法情况全部删去。
最终答案为 $G_0+G_1+G_2$。
上述三类根度数互不相同，且覆盖所有可能，故统计不重不漏。
模数记为 $p=10^9+7$。
所有组合数的下标都小于 $p$，由 Lucas 定理：
$$
\binom{n}{k}\equiv
\begin{cases}
\binom{n\bmod p}{k} & n\bmod p\ge k \\
0 & n\bmod p<k
\end{cases}
\pmod p
$$
因此只需保存各个树形数对 $p$ 的余数。
预处理阶乘后，大部分组合数可以常数时间求出。
当上标超过预处理范围时，题目限制保证下标至多约为 $10^3$，
直接连乘即可。
每组数据递归 $O(\log_B(R+1))$ 层，
空间主要用于阶乘与小底数的完整块答案表。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2000005;
const int K=1001;
const int H=31;
const int mod=1000000007;
int fac[N],ifac[N],f[K][H];
ll Pow(ll x,ll y)
{
x%=mod;
ll res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int fix(ll x)
{
return int((x%mod+mod)%mod);
}
int C(int n,int m)
{
if(n<m)return 0;
if(n<N)return int((ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod);
ll res=ifac[m];
for(int i=0;i<m;i++)res=res*(n-i)%mod;
return int(res);
}
int full(int b,int h)
{
if(h==0)return 1;
if(h==1)return b;
if(b<K)return f[b][h];
return fix(C(fix(2LL*b),b)-1);
}
int prefix(int b,int h,ll len,ll pw)
{
if(len==0)return 0;
if(h==1)return int(len);
int cnt=int(len/pw);
ll rem=len%pw;
int u=full(b,h-1);
ll res=C(fix((ll)u+cnt),cnt)-1;
if(rem==0)return fix(res);
int a=prefix(b,h-1,rem,pw/b);
res+=C(fix((ll)u+cnt),cnt+1)-C(fix((ll)u-a+cnt),cnt+1);
return fix(res);
}
int work(int b,int h,ll l,ll r,ll pw)
{
if(h==1)return int(r-l+1);
if(l/pw==r/pw)return work(b,h-1,l%pw,r%pw,pw/b);
ll x=pw-l%pw;
ll y=r%pw+1;
int a=prefix(b,h-1,x,pw/b);
int c=prefix(b,h-1,y,pw/b);
int z=prefix(b,h-1,min(x,y),pw/b);
int u=full(b,h-1);
int v=fix((ll)a+c-z);
int cnt=int(r/pw-l/pw-1);
ll ans=C(fix((ll)u+cnt),cnt)-1;
ans+=C(fix((ll)u+cnt),cnt+1)-C(fix((ll)u-v+cnt),cnt+1);
ans+=C(fix((ll)u+cnt+1),cnt+2)-C(fix((ll)u-a+cnt+1),cnt+2);
ans-=C(fix((ll)u-c+cnt+1),cnt+2)-C(fix((ll)u-v+cnt+1),cnt+2);
ans-=(ll)z*C(fix((ll)u-v+cnt),cnt+1)%mod;
return fix(ans);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
fac[0]=1;
for(int i=1;i<N;i++)fac[i]=int((ll)fac[i-1]*i%mod);
ifac[N-1]=int(Pow(fac[N-1],mod-2));
for(int i=N-1;i;i--)ifac[i-1]=int((ll)ifac[i]*i%mod);
for(int i=2;i<K;i++)
{
f[i][0]=1;
f[i][1]=i;
ll pw=(ll)i*i;
for(int j=2;pw<=1000000000;pw*=i,j++)f[i][j]=fix(C(fix((ll)f[i][j-1]+i),i)-1);
}
int T;
cin>>T;
while(T--)
{
int b;
ll l,r;
cin>>b>>l>>r;
int h=1;
ll pw=1;
while(pw*b<=r){pw*=b;h++;}
cout<<work(b,h,l,r,pw)<<'\n';
}
return 0;
}
```