Problem Link

题目大意

给定 $n$ 个负半轴上的动点和 $m$ 个正半轴的动点，初始位置为 $l_1\sim l_n,r_1\sim r_m$，每个点以 $1$ 的速度远离原点。

一个人从原点次以 $2$ 的速度抓捕最近的正半轴或负半轴上的点，对于每种抓捕顺序求出花费时间之和。

数据范围：$n,m\le 2.5\times 10^5$。

思路分析

事实上我们只关心所有抓捕后转向的点 $a_1\sim a_k$（包含最后一个抓到的点）。

那么设抓到 $a_i$ 的时刻是 $t_i$，由于 $a_{i+1}$ 一定和 $a_i$ 不同方向，因此当前两点距离为 $|a_i|+|a_{i+1}|+2t_i$，因此 $t_{i+1}=t_i+|a_i|+|a_{i+1}|+2t_i$。

化简得到 $t_k=|a_k|+\sum_{i<k}(3^{k-i-1}+3^{k-i})|a_i|$。

我们只考虑 $a$ 为 $l_i$ 的情况，剩余情况是对称的。

枚举 $k$，并枚举 $l_{1}\sim l_{i-1},l_{i+1}\sim l_n$ 选了几个进入 $a$，以及 $r_1\sim r_{m-1}$ 选了几个进入 $a$。

因为 $l_n,r_{m}$ 一定是 $a_k,a_{k-1}$ 之一，因此特殊讨论，$l_1\sim l_{n-1}$ 的答案为：

$$\dfrac 43\sum_{i=1}^{n-1}l_i\sum_{k=1}^n\left(\binom{m-1}{k-2}+4\binom{m-1}{k-1}+3\binom{m-1}k\right)\sum_{j=1}^{n-1}9^j\binom{n-i-1}{j-1}\binom{i-1}{k-j-1}$$

$l_n$ 的贡献为：

$$l_n\sum_{k=1}^{n-1}\binom{m-1}{k-2}+5\binom{m-1}{k-1}+4\binom{m-1}k$$

下面的式子容易算，我们只要快速计算上式，考虑单个 $\binom{m-1}{k-s}$ 的贡献，其中 $s\in\{0,1,2\}$，交换求和顺序后把 $k$ 的枚举用范德蒙德卷积替换得到：

$$\sum_{k=1}^n\binom{m-1}{k-s}\sum_{j=1}^{n-1}9^j\binom{n-i-1}{j-1}\binom{i-1}{k-j-1}=\sum_{j=1}^{n-1}9^j\binom{n-i-1}{j-1}\binom{m+i-2}{m-j+s-2}$$

不难用 NTT 优化计算。

时间复杂度 $\mathcal O((n+m)\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353,N=1<<19,G=3;
int fac[N],ifac[N];
namespace P {
int rev[N],inv[N],w[N<<1];
int ksm(int a,int b=MOD-2) {
	int ret=1;
	for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;
	return ret;
}
void poly_init() {
	inv[1]=1;
	for(int i=2;i<N;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
	fac[0]=ifac[0]=1;
	for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;
	for(int k=1;k<=N;k<<=1) {
		int x=ksm(G,(MOD-1)/k); w[k]=1;
		for(int i=1;i<k;++i) w[i+k]=1ll*x*w[i+k-1]%MOD;
	}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {
	for(int i=0;i<n;++i) {
		rev[i]=(rev[i>>1]>>1);
		if(i&1) rev[i]|=n>>1;
	}
	for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);
	for(int k=2,x,y;k<=n;k<<=1) {
		for(int i=0;i<n;i+=k) {
			for(int j=i;j<i+k/2;++j) {
				x=f[j],y=1ll*f[j+k/2]*w[k+j-i]%MOD;
				f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;
			}
		}
	}
	if(idft) {
		reverse(f+1,f+n);
		for(int i=0,x=ksm(n);i<n;++i) f[i]=1ll*f[i]*x%MOD;
	}
}
}
using P::ntt;
int C(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
int n,m,w[N],a[N],b[N],pw[N];
const int cof[3]={3,4,1},i3=(MOD+1)/3; //cof of C(m-1,x-k)
int solve() {
	int ans=0;
	memset(a,0,sizeof(a));
	for(int i=1;i<n;++i) a[i]=1ll*w[i]*fac[m+i-2]%MOD*fac[n-i-1]%MOD;
	ntt(a,0,N);
	for(int k:{0,1,2}) {
		memset(b,0,sizeof(b));
		for(int j=1;j<n&&m-j+k-2>=0;++j) b[j]=1ll*pw[j]*ifac[j-1]%MOD*ifac[m-j+k-2]%MOD;
		ntt(b,0,N);
		for(int i=0;i<N;++i) b[i]=1ll*a[i]*b[i]%MOD;
		ntt(b,1,N);
		for(int s=k;s<=n;++s) ans=(ans+1ll*cof[k]*b[s]*ifac[n-s]%MOD*ifac[s-k])%MOD;
	}
	ans=4ll*ans*i3%MOD;
	for(int i=1;i<=n;++i) ans=(ans+(5ll*C(m-1,i-1)+4ll*C(m-1,i)+C(m-1,i-2))%MOD*w[n]%MOD*C(n-1,i-1))%MOD;
	return ans;
}
signed main() {
	P::poly_init();
	for(int i=pw[0]=1;i<N;++i) pw[i]=9ll*pw[i-1]%MOD;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	int ans=solve();
	for(int i=1;i<=m;++i) scanf("%d",&w[i]);
	swap(n,m);
	printf("%d\n",(ans+solve())%MOD);
	return 0;
}