#组合计数,卢卡斯定理#D 三元组

题目

(z=0)时,(f(x,y,z)=1)
否则

[f(x,y,z)=sum_{x1=1}^xsum_{y1=1}^y(x-x1+1)(y-y1+1)f(x1,y1,z-1) ]

[sum_{x=1}^nsum_{y=1}^mf(x,y,k) ]

对998244353取模,(n,m,kleq 10^18)


分析

考时发现将(f(1,1)=1)后跑(2k+2)次前缀和后(f(n,m))就是答案,
所以题目就简化成(k)阶前缀和的答案就是(f(i+k-1,k-1))
以下是北爷的证明

然后套个卢卡斯定理貌似就能玄学了

原文地址:https://www.cnblogs.com/Spare-No-Effort/p/14081279.html