暑期实习公司打分

T1 大分讨,不过没太讨论清楚T2 不会ML，oh noT3 先容斥变成求解长为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 赛后才调完