众所周知有经典问题：\(T\) 组询问 \(\sum_{i=0}^m \binom{n}{i}\)。听说戴老师一年多前就有个 \(n \log^2 n\) 的做法，感觉很厉害，但是搜不到做法，也想尝试自己推推。
今天受到了一些启发，好像推出了个 \(\Theta(n \log^2 n)\) 的做法（未经验证 QAQ），感觉很厉害，就来写篇博客。
很酷的第一步：设 \(f_m(x) = \sum_{i=0}^m \frac{\prod_{j=0}^{i-1} (x-j)}{i!}\)，要求的就是 \(f_m(n)\)。
这就意味着假设我们把这个多项式丢到线段树上，多次多点求值就是 \(\Theta(n \log^3 n)\) 的。
仔细思考一下就会发现是因为重复的点值，复杂度高了。考虑如何避免：我们直接把答案写成 \(\sum_{i=0}^m \frac{\prod_{j=0}^{i-1} (x-j)}{i!} \bmod (x-n)\)。
直接在线段树上做分治取模就是 \(\Theta(n \log^2 n)\) 的啦。
看起来这篇博客有点短，但是感觉这个做法很酷！！！