CF1096E [* easy]
有 (n) 个随机变量，每个变量均为一个非负整数，第一个随机变量的值大于等于 (m)，且随机变量的权值和为 (S)
假设一个随机变量为最大值，那么说这个变量 win 了，如果有多个随机变量为最大值，那么就随机说一个变量 win 了。
求第一个变量 win 的概率。答案对 (998244353) 取模。
(n,Sle 5000,mle 100)
Solution
令 (n-1)，然后枚举第一个变量的值 (x)，其余元素的最大值和他权值相同的数量：
[sum_{xge m} sum_i frac{1}{i+1}inom{n}{i}F(x-1,n-i,S-(i+1) imes x)
]
其中 (F(a,b,c)) 表示使用 ([0,a]) 分配给 (b) 个人使权值和为 (c) 的方案数。((1+x+x^2+...+x^a)^b[x^c])
即：
[egin{aligned}
&(frac{1-x^{a+1}}{1-x})^b[x^c]
\&=frac{1}{(1-x)^b} imes (1-x^{a+1})^b[x^c]
\&=frac{1}{(1-x)^b} imes sum_j inom{b}{j}x^{j(a+1)}(-1)^j[x^c]
\&=sum_j inom{b}{j}(-1)^j imes inom{c-j(a+1)+b-1}{b-1}
end{aligned}]
不难发现我们的外层枚举量为 (mathcal O(nlog n))
对于内层，单次计算的枚举量为 (min(frac{c}{a+1},b))
所以总枚举量即：
[sum_{xge m} sum_i^{ixle S} min(n,frac{S}{x})
]
其实也是 (sum frac{S^2}{x^2}) 大约是 (S^2)（(sum_i frac{1}{i^2}=frac{pi^2}{6})。
分母的话大概是 (sum_{xge m} frac{1}{(1-x)^n}[x^{S-x}]=sum_{xge m}inom{n+S-x-1}{n-1})。