题面描述
求
答案对(998244353)取模
数据范围
对于(100\%)的数据，(rle 10000000)，(mle 10000000)
样例输入
114514 1919810
样例输出
996103057
解题思路：
对于里层
我们进行化简
首先对于分母不受(sum)的影响因此我们只用管分子即可，即化简
首先对于组合数我们运用(egin{aligned}dbinom{n}{m}=dbinom{n-1}{m-1} imes frac{n}{m}end{aligned})可以得到(egin{aligned}(m-k)dbinom{m-k-1}{m-n-1}=(m-n)dbinom{m-k}{m-n}end{aligned})
随后我们要想运用此公式要提出((m-k))，因此我们将(k)写成(m-(m-k))
则有(egin{aligned}sum_{k=0}^{n}k imes dbinom{m-k-1}{m-n-1}=sum_{k=0}^{n}(m-(m-k)) imes dbinom{m-k-1}{m-n-1}=msum_{k=0}^{n}dbinom{m-k-1}{m-n-1}-sum_{k=0}^{n}(m-k) imes dbinom{m-k-1}{m-n-1}=mA-(m-n)Bend{aligned})
对于(egin{aligned}A=sum_{k=0}^{n}dbinom{m-k-1}{m-n-1}end{aligned})，(egin{aligned}B=sum_{k=0}^{n}dbinom{m-k}{m-n}end{aligned})
到这里就很简单了，对于(B)的话我们(egin{aligned}B=sum_{k=0}^{n}dbinom{m-k}{m-n}=sum_{m-k=0}^{n}dbinom{m-(m-k)}{m-n}=sum_{k=m-n}^{m}dbinom{k}{m-n}=sum_{k=0}^{m}dbinom{k}{m-n}end{aligned})
然后到这里我们可以得到(egin{aligned}B=sum_{k=0}^{m}dbinom{k}{m-n}=dbinom{m+1}{m-n+1}end{aligned})，读者自证不难
对于(A)我们的处理方法相同，但用(m-1)来代替(m)。
因此原柿子继续化简为(egin{aligned}mA-(m-n)B=mdbinom{m}{m-n}-(m-n)dbinom{m+1}{m-n+1}=(m-(m-n) frac{m+1}{m-n+1})dbinom{m}{m-n}=frac{n}{m-n+1}dbinom{m}{m-n}end{aligned})
则我们有(egin{aligned}frac{frac{n}{m-n+1}dbinom{m}{m-n}}{dbinom{m}{n}}=frac{n}{m-n+1}end{aligned})
随后此题就可以(O(n))做了