标签:数学-扩展卢卡斯定理

LOJ最优解达成!题意求满足下列要求的长度为 $2n$ 的序列 $S$ 的个数,对 $p$ 取模:是 $2n$ 的全排列奇数项、偶数项分别递增$\forall i\in [1,n] \ , \ S_{2i-1} < S_{2i}$题解对于性质 $2$ ,可以考虑将 $1...2n$ 的数字按照从小到大的顺序依次放入序列。每个数字可以放在最前的奇数或偶数位。分析性质 $3$ ,显然偶数位...
题解 数学 数学-扩展卢卡斯定理 数学-卡特兰数
省选/NOI-
概述卢卡斯定理主要用于求解组合数取模问题。公式原命题见: https://zh.wikipedia.org/wiki/%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%AE%9A%E7%90%86原命题等价于:$$\binom{m}{n}=\binom{\lfloor \dfrac{m}{p}\rfloor}{\lfloor \dfrac{n}{p}\rfloor}\times ...
题意把 $n$ 个不同的礼物分给 $m$ 个人,每个人 $w_i$ 个,求方案数 $\mod p$ 的值。其中 $n,p\le 10^{9}$ ,$m\le 5$ 。题解答案显然为:$$\prod _{i=1}^m C(n-\sum_{i=1}^m w_i,w_i)\mod p$$因为 $p$ 不一定是质数,所以直接上 $\text{exLucas}$ 就行了。#include<bit...
题解 数学 数学-扩展卢卡斯定理
NOI/NOI+/CTSC