「BZOJ2142」 礼物/exLucas
题目链接 题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。 对于这一类题目，我们有一种叫做 exlucas 的方法来算组合数（但是和 lucas 没有半毛钱关系）。 首先我们将模数 $m$ 质因数分解，最后用 CRT 合并一下就好了。 然后我们现在只需要考虑组合数对 $p^e$ 取模的情况了。 这样还是不能直接去乘逆元的，因为分母可能有因子 $p$，直接求逆元会变成 $0$ ...
题目链接 题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。 对于这一类题目，我们有一种叫做 exlucas 的方法来算组合数（但是和 lucas 没有半毛钱关系）。 首先我们将模数 $m$ 质因数分解，最后用 CRT 合并一下就好了。 然后我们现在只需要考虑组合数对 $p^e$ 取模的情况了。 这样还是不能直接去乘逆元的，因为分母可能有因子 $p$，直接求逆元会变成 $0$ ...
题意：求$a^x \equiv b(\mod p^e)$ 的最小整数解。 $3 < p \leq 50,p^e \leq 10^18,a\nmid p,b \nmid p$，询问不超过 $1000$ 组。暴力分跑 bsgs 其实就可以了...因为保证了 $(a,p^e) = 1$。 但是这样显然会 T，于是我们就不要往 bsgs 的方面去想了。 我们考虑 $p$ 很小并且 $>2$，这...
题目描述：给你若干条形如 $x+y=c$ 或 $x-y=c$ 的直线，这些直线与坐标轴的夹角是 45 度，问在矩形 $(0,0) \to (W,H)$ 中，有多少个子矩形。图片示意：上图有 $19$ 个子矩形。$n \leq 10^5$首先这一题目 $O(n^3)$ 的复杂度十分好做：就是枚举三条边 去 map 找一下第四条边就好了。我们考虑如何做到 $O(n^2logn)$:我们可以考虑先...
最近从某个地方看到了这个题。。。所以回来补一下题解。题目描述 题解直接求期望不太好求，我们可以考虑求出每一种条件下的概率，最后乘上直径长度就可以了。 我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里，目前不跨过 $i$ 节点的最长链是 $j$，子树的直径是 $k$ 的概率。 转移就用树 dp 合并子树那种方法来做...枚举一下根与待合并的子树之间的边权就可以了。 转移方程就咕了...