final_d

高橋君 给定若干个 \(n,m\)，求 \(\sum\limits_{i=0}^{m} \dbinom{n}{i}\)。为方便，记 \(C(n,m)=\dbinom{n}{m},S(n,m)=\sum\limits_{i=0}^{m} C(n,i)\)。 我们知道 \(C(n,m)=C(n-1,m- ......

AT_ddcc2020_final_d Pars/ey 重工业题。 找环然后树形 DP 是显然的，先考虑断开环上的边怎么做。 把环复制一遍放在结尾，记 \(sum_i\) 为环长的前缀和，\(f_i\) 为该子树内的最长根链的长度，问题变为每次给定一个区间，要求找到 \(i,j(i>j)\) 使得 ......

和上一题类似不过这道题不能再使用Lucas定理了。 即$m$组询问 $\sum_{i=0}^kC(n,i)\%\ 1e9+7,n,m,k\le 100000$ 这是一个很经典的莫队求组合数的和的问题。 因为有两个指针$l,r$ 显然需要处理四种情况： $l,r->l+1,r$此时加上$C(r,l+1 ......