题目
题目描述
ρ有一个函数$f(i,j)$
当$i>0$且$j>0$时，有$f(i,j)=f(i,j-1) \times a+f(i-1,j) \times b$ρ告诉你了$n,m,a,b,f(i,0)(1 \leqslant i \leqslant n),f(0,i)(1 \leqslant i \leqslant m)$ρ也要你告诉他$f(n,m)$
不过ρ很善良，他只要知道$f(n,m)mod998244353$
这样你就不用打工业的高精度（？？？）
输入格式
第一行：四个正整数$n,m,a,b$
第二行：$n$个正整数，第$i$个表示$f(i,0)$
第三行：$m$个正整数，第$i$个表示$f(0,i)$
输出格式
第一行：一个整数，代表$f(n,m)mod998244353$
样例
样例输入
1 | 4 4 3 2 |
样例输出
1 | 50807 |
数据范围与提示
$20 \%$的数据：$n,m \leqslant 10,a,b \leqslant 3,f(i,0),f(0,i) \leqslant 10$
$50 \%$的数据：$n,m \leqslant 10^3$
另外$10 \%$的数据：$n=1$
另外$10 \%$的数据：$a=b=1$
另外$10 \%$的数据：$f(i,0)=f(0,i)=1$
$100 \%$的数据：$n,m \leqslant 3 \times 10^5$，其他所有输入数据均在long long范围内
题解
刚看到题目，就让我想到了以前的一道题：DTOJ3603 table
这道题也是一样的道理，只需要计算边界点到这个点的路径条数，再乘以$a$的次方，$b$的次方
唯一要注意的点是：边界上是不满足递推式的，所以第一步的方向是确定的
通过计算，我们可以得出递推式：
$f_{i,0}$的贡献是：$f_{i,0}\times \binom{m-1}{n+m-1-i}\times a^m\times b^{n-i}$
$f_{0,i}$的贡献是：$g[i]\times \binom{n-1}{n+m-1-i}\times a^{m-i}\times b^n$
附上代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n,m;
long long a,b,ans,MOD=998244353,f[600010],g[600010],jc[600010],cj[600010],pa[600010],pb[600010];
long long POW(long long a,long long b)
{
long long ans=1;
for(;b;b>>=1){
if(b&1) ans=(ans*a)%MOD;
a=(a*a)%MOD;
}
return ans;
}
long long C(int x,int y)
{
if(x<0||y<0||x>y) return 0;
return jc[y]*cj[x]%MOD*cj[y-x]%MOD;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d%d%lld%lld",&m,&n,&a,&b),a=a%MOD,b=b%MOD;
for(int i=1;i<=m;i++) scanf("%lld",&f[i]),f[i]=f[i]%MOD;
for(int i=1;i<=n;i++) scanf("%lld",&g[i]),g[i]=g[i]%MOD;
jc[0]=pa[0]=pb[0]=1;
for(int i=1;i<=600000;i++) jc[i]=jc[i-1]*i%MOD;
cj[600000]=POW(jc[600000],MOD-2);
for(int i=599999;i>=0;i--) cj[i]=cj[i+1]*(i+1)%MOD;
long long na=POW(a,MOD-2),nb=POW(b,MOD-2);
for(int i=1;i<=600000;i++) pa[i]=pa[i-1]*a%MOD,pb[i]=pb[i-1]*b%MOD;
for(int i=1;i<=m;i++) ans=(ans+f[i]*C(n-1,n+m-1-i)%MOD*pa[n]%MOD*pb[m-i]%MOD)%MOD;
for(int i=1;i<=n;i++) ans=(ans+g[i]*C(m-1,n+m-1-i)%MOD*pa[n-i]%MOD*pb[m]%MOD)%MOD;
printf("%d",ans);
}