自动搬运

查看原文

来自洛谷，原作者为

	Kubic Go straight ahead 'til we've lost it all.

搬运于2025-08-24 22:50:44，当前版本为作者最后更新于2023-12-14 17:23:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这是一个不需要 NTT 的 $O(n\log n)$ 做法。

令 $f_{n,k,m}$ 表示第 $k$ 个点被覆盖的方案数。考虑其 EGF：

$$F_{n,k}(x)=\sum\limits f_{n,k,i}\dfrac{x^i}{i!}$$

令 $n_1=\left\lfloor\dfrac{n-1}{2}\right\rfloor,n_2=\left\lfloor\dfrac{n}{2}\right\rfloor$。

$f_{n,k,m}$ 的转移式容易得到，经过变换可以得到 $F_{n,k}(x)$ 的转移式：

若 $n$ 为奇数，则：

$$F_{n,k}(x)=1+\int n(F_{n_1,k}(x)\times (1+x)^{n_2}+F_{n_2,k-n_1-1}(x)\times (1+x)^{n_1}) $$

若 $n$ 为偶数，则：

$$F_{n,k}(x)=1+\int\dfrac{n}{2}(F_{n_1,k}(x)\times (1+x)^{n_2}+F_{n_2,k-n_1-1}(x)\times (1+x)^{n_1} $$$$+F_{n_2,k}(x)\times (1+x)^{n_1}+F_{n_1,k-n_2-1}(x)\times (1+x)^{n_2}) $$

其中积分运算要求运算后常数项为 $0$。出现积分的原因是我们初始花掉了一次操作，这次操作并不会在合并两棵子树时被统计在内。加入这一次操作在 OGF 的意义下为 $F\leftarrow xF$，在 EGF 的意义下即为 $F\leftarrow\int F$。

可以发现，转移过程中涉及到本质不同的长度相当于线段树上节点长度的种类数，数量为 $O(\log n)$。同时可以得到这些长度总和为 $O(n)$，因此我们只会涉及到 $O(n)$ 个状态。

我们考虑快速地计算出所有可能涉及到的 $F_{n,k}(x)$。

将 $F_{n,k}(x)$ 看作 $\sum a_p(1+x)^p$。我们有：

$$\int(1+x)^q=\dfrac{1}{q}(1+x)^q-\dfrac{1}{q}$$

观察转移的特性，可以发现 $a_p\neq 0$ 的 $p$ 只可能为某个 $n-n'$，其中 $n'$ 是某个递归到的长度（积分过程中多出来的 $p=0$ 的一项恰好可以被归入到 $n=n'$ 的情况）。由上面的分析可得只有 $O(\log n)$ 个可能的 $p$！

因此每个 $F_{n,k}(x)$ 在转为上述形式之后均可以被表示为 $O(\log n)$ 项之和。

而上述转移中所有操作均可在与项数同阶的时间复杂度内完成。因此一次转移的时间复杂度为 $O(\log n)$。总时间复杂度为 $O(n\log n)$。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5,M=45,MOD=998244353,inv2=499122177;
int n,n1,n2,m,c,tmp,a[N],id[N],o[N],fc[N],invFc[N];bool vs[N];
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
void W(int &x,ll y) {x=(x+y)%MOD;}
int add(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
struct Node
{
	int z[M];
	void trs(int x)
	{int t=0;for(int i=1;i<x;++i) z[i]=1ll*z[i]*o[i]%MOD,W(t,z[i]);W(z[x],MOD-t);}
	int eval(int x,int y)
	{
		int res=0;
		for(int i=1;i<=x;++i) if(a[x]-a[i]>=y)
			W(res,1ll*z[i]*fc[a[x]-a[i]]%MOD*invFc[a[x]-a[i]-y]);return res;
	}
};vector<Node> dp[M];
Node operator + (const Node& a,const Node& b)
{Node res;for(int i=1;i<=m;++i) res.z[i]=add(a.z[i],b.z[i]);return res;}
int qPow(int x,int y)
{int res=1;for(;y;y/=2,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD;return res;}
void init(int n)
{
	fc[0]=invFc[0]=1;for(int i=1;i<=n;++i) fc[i]=1ll*fc[i-1]*i%MOD;
	invFc[n]=qPow(fc[n],MOD-2);
	for(int i=n-1;i;--i) invFc[i]=1ll*invFc[i+1]*(i+1)%MOD;
}
int bn(int x,int y) {return x<y?0:1ll*fc[x]*invFc[y]%MOD*invFc[x-y]%MOD;}
void trs(int x,int x1,int x2)
{
	for(int i=1;i<=a[x];++i) if(i<=a[x1]) dp[x][i]=dp[x][i]+dp[x1][i];
		else if(i>a[x1]+1) dp[x][i]=dp[x][i]+dp[x2][i-a[x1]-1];
}
int main()
{
	scanf("%d %d",&n,&c);n1=n2=n;init(n);tmp=1ll*invFc[n]*fc[n-c]%MOD;
	while(n2) {if(!vs[n2]) vs[a[++m]=n2]=1;if(!vs[n1]) vs[a[++m]=n1]=1;n1=(n1-1)/2;n2/=2;}
	reverse(a+1,a+m+1);
	for(int x=1,x1,x2,t;x<=m;++x)
	{
		dp[x].resize(a[x]+1);if(!a[x]) continue;
		x1=0;for(int i=x;i;--i) if(a[i]==(a[x]-1)/2) {x1=i;break;}
		x2=0;for(int i=x;i;--i) if(a[i]==a[x]/2) {x2=i;break;}
		trs(x,x1,x2);trs(x,x2,x1);t=1ll*a[x]*inv2%MOD;
		for(int i=1;i<=x;++i) o[i]=qPow(a[x]-a[i],MOD-2)%MOD;
		for(int i=1;i<=a[x];++i)
		{
			dp[x][i].trs(x);for(int j=1;j<=x;++j) dp[x][i].z[j]=1ll*dp[x][i].z[j]*t%MOD;
			W(dp[x][i].z[x],1);
		}
	}for(int i=1;i<=n;++i) printf("%d\n",add(MOD-(1ll*dp[m][i].eval(m,c)*tmp)%MOD,1));return 0;
}