美团第四场笔试小记

T1 大分讨,不过没太讨论清楚
T2 不会ML，oh no

T3 先容斥变成求解长为m,取值[1,v] 总和为k的数组，考虑用如下的生成函数描述总和为k的个数：
[x^k] (\frac{x *(1-x^v)}{1- x})^m
= [x^{k - m}] (1-x^v)^m  \cdot  (1-x)^{-m}
前者二项式系数展开，后者牛顿二项式系数展开，枚举前一项x的系数为x^{iv}, 可得：
ans = \sum_{i = 0, r = k - m - iv}^{iv \leq k - m} (-1)^i C(m, i) C(m + r - 1,r)
最后ans <-   v^n - ans 即可, 注意n根据费马小定理要对P - 1取模，或者直接传i64
复杂度O(\sum m + log P)

T4, 一个基环树，考虑将答案拆为3部分：
1. 链， 2. 若干次整个环， 3 部分环
我们先通过dfs求得基环树的环和链，用倍增维护链上的父节点和其他信息，复杂度O(nlogn)
1.如果k > 链长，直接跳到根节点，进入2部分
否则，倍增上跳的过程中求和即可，O(log n)
2/3 若环长为len，还剩k步，则我们走x = k / len个整环，y = k % len 一部分长的环
于是贡献就是 x(x+1)/2 * all(circle) + (x + 1) * getcir(p, p + y - 1), 求解这部分是O(1)的
总复杂度是O(nlogn + qlogn)
可惜T4 赛后才调完

#美团笔试##一起聊美团##笔试#