【2025NOI模拟赛01】青蛙 做题记录

你在一个二维平面上，刚开始在 $(0,0)$。你可以在平面的第一象限（包括坐标轴）中走路，若当前在 $(x,y)$，则你可以：

• 走到 $(x+1,y-1)$（前提是 $y-1\ge0$）：贡献为 $Ay^2$；
• 走到 $(x+1,y)$：贡献为 $By+Cx$；
• 走到 $(x+1,y+1)$：贡献为 $D$；

定义一条路径的权值为每一步的贡献积。

给定 $n,m,A,B,C,D$，求从 $(0,0)$ 走到 $(n,m)$ 的所有路径的权值和，对 $998244353$ 取模。

$0\le m\le n\le 2.5\times 10^5$，$0\le A,B,C,D\le 998244352$。

• $(x+1,y+1)$：加入一个黑点并不连边，贡献为 $D$；

• $(x+1,y)$：加入一个白点，并选一个之前的点作为父亲，若连接的是黑点，则贡献为 $B+C$，否则贡献为 $C$；

• $(x+1,y-1)$：

  首先 $Ay^2=A(2\binom{y}{2}+y)$；

  无序地选择两棵树，让树根的黑点变为白点，并以一个新建的黑点为父亲，贡献为 $2A$；

  选择一棵树，让树根的黑点变为白点，并以一个新建的白点为父亲，贡献为 $A$；

那么设 $f_n$ 表示根为白点，大小为 $n$ 的树的方案数，同理设 $g_n$ 表示根为黑点的，考虑最后一个点干了什么：

• $f_n=C(n-1)f_{n-1}+Ag_{n-1}$；
• $g_n=(C(n-1)+B)g_{n-1}+2A\sum\limits_{i=1}^{n-2}g_ig_{n-1-i}\binom{n-2}{i-1}$，最后那个 sigma 是枚举 $n-1$ 所在的树；

显然 $f_0=f1=g_0=0,g_1=D$，则：

• $f_n=C(n-1)f_{n-1}+Ag_{n-1}$；
• $g_n=(C(n-1)+B)g_{n-1}+2A\sum\limits_{i=0}^{n-1}g_{i}g_{n-1-i}\binom{n-2}{i-1}=(C(n-1)+B)g_{n-1}+\frac{2A}{n-1}\sum\limits_{i=0}^{n-1}g_{i}g_{n-1-i}\binom{n-1}{i}\times i$；

显然求出 $g$ 后就可以 $O(n)$ 求出 $f$，而 $g$ 可以分治 NTT $O(n\log ^2n)$ 求。

注意这个分治 NTT 是自己卷自己的形式。

代码如下：

const int S=250005;

int fra[S],inv[S];
int n,m,a,b,c,d;
int g[S],f[S];
ploy F,G;

inline int qinv(int x){return 1ll*inv[x]*fra[x-1]%p;}

void slove(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	slove(l,mid);
	if(l==1)
	{
		// [1,mid]*[0,mid]
		ploy lft,tmp;
		lft.resize(mid),tmp.resize(mid+1);
		for(int i=1;i<=mid;i++) lft[i-1]=1ll*g[i]*inv[i-1]%p;
		for(int i=0;i<=mid;i++) tmp[i]=1ll*g[i]*inv[i]%p;
		lft=lft*tmp;
		for(int i=mid+1;i<=r;i++)
		{
			int pre=1ll*2*a*qinv(i-1)%p*lft[i-l-1]%p*fra[i-1]%p;
			add(g[i],pre);
		}
	}
	else
	{
		// [l,mid]*[0,r-l]
		ploy lft,tmp;
		lft.resize(mid-l+1),tmp.resize(r-l+1);
		for(int i=l;i<=mid;i++) lft[i-l]=1ll*g[i]*inv[i-1]%p;
		for(int i=0;i<=r-l;i++) tmp[i]=1ll*g[i]*inv[i]%p;
		lft=lft*tmp;
		for(int i=mid+1;i<=r;i++)
		{
			int pre=1ll*2*a*qinv(i-1)%p*lft[i-l-1]%p*fra[i-1]%p;
			add(g[i],pre);
		}
		// [1,r-l]*[l,mid]
		lft.resize(r-l+1),tmp.resize(mid-l+1);
		lft[0]=0;
		for(int i=1;i<=r-l;i++) lft[i]=(1ll*g[i]*inv[i-1]%p);
		for(int i=l;i<=mid;i++) tmp[i-l]=(1ll*g[i]*inv[i]%p);
		lft=lft*tmp;
		for(int i=mid+1;i<=r;i++)
		{
			int pre=1ll*2*a*qinv(i-1)%p*lft[i-l-1]%p*fra[i-1]%p;
			add(g[i],pre);
		}
	}
	add(g[mid+1],(1ll*c*mid%p+b)*g[mid]%p);
	slove(mid+1,r);
}

int main()
{
	freopen("frogs.in","r",stdin);
	freopen("frogs.out","w",stdout);
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	inv[S-3]=qpow(fra[S-3],p-2);
	for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d);
	g[0]=0,g[1]=d;
	slove(1,n);
	f[0]=f[1]=0;
	for(int i=2;i<=n;i++)
	{
		f[i]=1ll*c*(i-1)%p*f[i-1]%p;
		add(f[i],1ll*a*g[i-1]%p);
	}
	for(int i=0;i<=n;i++)
	{
		F.push_back(1ll*f[i]*inv[i]%p);
		G.push_back(1ll*g[i]*inv[i]%p);
	}
	F=exp(F),G=pow2(G,m,m);
	F=F*G;
	printf("%d\n",1ll*F[n]*fra[n]%p*inv[m]%p);
	return 0;
}