卢卡斯定理
![【BZOJ4591】[SHOI2015]超能粒子炮·改 （卢卡斯定理）](/scriptcss/images/61.png)
【BZOJ4591】[SHOI2015]超能粒子炮·改 （卢卡斯定理）
【BZOJ4591】[SHOI2015]超能粒子炮·改 （卢卡斯定理） 题面 BZOJ 洛谷 题解 感天动地！终于不是拓展卢卡斯了！我看到了一个模数，它是质数！！！ 看着这个东西就感觉可以递归处理。 令\(f(n,k)\)表示答案。 \[\begin{aligned} f(n,k)&=\sum_{i=0}^k {n\choose i}\\ &=\sum_{i=0}^k {n/p\
日期 2023-06-12 10:48:40![【BZOJ4830】[HNOI2017]抛硬币（组合计数，拓展卢卡斯定理）](/scriptcss/images/65.png)
【BZOJ4830】[HNOI2017]抛硬币（组合计数，拓展卢卡斯定理）
【BZOJ4830】[HNOI2017]抛硬币（组合计数，拓展卢卡斯定理） 题面 BZOJ 洛谷 题解 暴力是啥？ 枚举\(A\)的次数和\(B\)的次数，然后直接组合数算就好了：\(\displaystyle \sum_{i=0}^a{a\choose i}\sum_{j=0}^{i-1}{b\choose j}\)。 完美\(TLE\)。 先考虑特殊点的情况，如果\(a=b\)，那么显然两者
日期 2023-06-12 10:48:40![【BZOJ3129】[SDOI2013]方程（容斥，拓展卢卡斯定理）](/scriptcss/images/64.png)
【BZOJ3129】[SDOI2013]方程（容斥，拓展卢卡斯定理）
【BZOJ3129】[SDOI2013]方程（容斥，拓展卢卡斯定理） 题面 BZOJ 洛谷 题解 因为答案是正整数，所先给每个位置都放一个就行了，然后\(A\)都要减一。 大于的限制和没有的区别不大，提前给他\(A_i\)个就好了。 假如没有小于的限制的话，那么就是经典的隔板法直接算答案。 如果提前给完之后，还剩\(M\)个球，要放进\(n\)个盒子，答案就是\(\displaystyle{M+
日期 2023-06-12 10:48:40
【BZOJ2142】礼物（拓展卢卡斯定理）
【BZOJ2142】礼物（拓展卢卡斯定理） 题面 BZOJ 洛谷 题解 显然如果\(\sum w_i>n\)无解。 否则答案就是：\(\displaystyle \prod_{i=1}^m{n-\sum_{j=0}^{i-1}w_j\choose w_i}\)。 因为并没有保证\(P\)是质数，所以需要用到拓展卢卡斯。 #include<iostream> #include&l
日期 2023-06-12 10:48:40
【BZOJ4903】【UOJ#300】吉夫特（卢卡斯定理，动态规划）
【BZOJ4903】【UOJ#300】吉夫特（卢卡斯定理，动态规划） 题面 UOJ BZOJ：给的UOJ的链接...... 题解 首先模的质数更小了，直接给定了\(2\)。当然是卢卡斯定理了啊。 考虑一个组合数在什么情况下会是一个奇数。\(Lucas(n,m)\equiv Lucas(n/2,m/2)*Lucas(n\%2,m\%2)\)。后面这个东西一共只有\(4\)种取值，我们大力讨论一下:
日期 2023-06-12 10:48:40【UOJ#275】组合数问题（卢卡斯定理，动态规划）
【UOJ#275】组合数问题（卢卡斯定理，动态规划） 题面 UOJ 题解 数据范围很大，并且涉及的是求值，没法用矩阵乘法考虑。 发现\(k\)的限制是，\(k\)是一个质数，那么在大组合数模小质数的情况下可以考虑使用卢卡斯定理。 卢卡斯定理写出来是\(Lucas(n,m)=Lucas(n/K,m/K)*Lucas(n\%K,m\%K)\) 显然只要有任何一个\(Lucas(n\%K,m\%K)=
日期 2023-06-12 10:48:40【BZOJ1951】古代猪文（CRT，卢卡斯定理）
【BZOJ1951】古代猪文（CRT，卢卡斯定理） 题面 BZOJ 洛谷 题解 要求什么很显然吧。。。 \[Ans=G^{\sum_{k|N}{C_N^k}} \]给定的模数是一个质数，要求解的东西相当于是上面那坨东西的结果对于\(\varphi\)的取值。 但是\(\varphi\)不是质数，不好直接\(Lucas\)定理，把\(\varphi\)分解质因数之后， 直接\(CRT\)合并结果就
日期 2023-06-12 10:48:40【BZOJ4403】序列统计（组合数学，卢卡斯定理）
【BZOJ4403】序列统计（组合数学，卢卡斯定理） 题面 Description 给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。 Input 输入第一行包含一个整数T，表示数据组数。 第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。 1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R
日期 2023-06-12 10:48:40【Luogu3807】【模板】卢卡斯定理（数论）
题目描述 给定\(n,m,p(1≤n,m,p≤10^5)\) 求 \(C_{n+m}^m mod p\) 保证\(P\)为\(prime\) \(C\)表示组合数。 一个测试点内包含多组数据。 输入输出格式 输入格式： 第一行一个整数\(T(T≤10)\)，表示数据组数 第二行开始共\(T\)行，每行三个数\(n m p\)，意义如上 输出格式： 共\(T\)行，每行一个整数表示答案。 输入输出
日期 2023-06-12 10:48:40洛谷 P3807 【模板】卢卡斯定理
洛谷 P3807 【模板】卢卡斯定理 洛谷传送门 题目背景 这是一道模板题。 题目描述 给定整数 n, m, pn,m,p 的值，求出 C_{n + m}^n \bmod pC**n+m**nmodp 的值。 输入数据保证 pp 为质数。 注: CC 表示组合数。 输入格式 本题有多组数据。 第一行一个整数 TT，表示数据组数。 对于每组数据: 一行，三个整数 n, m, pn,m,p。 输出格
日期 2023-06-12 10:48:40