Loading...
阶与原根 阶 定义 1.1 (阶) 对于 $m \in \mathbb{N}^*, a \in [0, m), (a, m) = 1$，设 $n$ 为满足 $a^n \equiv 1 \pmod{m}$ 的最小正整数，则称 $n$ 为 $a$ 模 $m$ 的阶，记做 $\delta_m(a)$。 关于阶，我们给出如下定理： 定理 1.1 $a, a^2, \cdots, a^{\del...
Luogu LOJ 分析 由 Lucas 定理可以推出，${n\choose m}\bmod 1\equiv{2}$ 当且仅当 $n \& m = m$。这样子很容易有一个 $\mathcal{O}(n^2)$ 的 DP。 为了方便，我们倒过来 DP，则要求上一个数是这一个数的子集，直接枚举子集转移即可。 复杂度是 $\mathcal{O}(3^{\log A})$ 的。 代码 //...