Harris-H

组合数学

BFS(5) CF题解(3) DFS(20) DP(20) LCA(2) Leetcode(1) Nowcoder题解(4) ST(1) Tarjan(1) 二分(4) 二分法(1) 二叉树题目(4) 位运算(2) 前缀和(4) 博弈论(3) 图论(1) 字符串(5) 学习笔记(1) 并查集(2) 快速幂(1) 思维(7) 排序(1) 数状数组(3) 数论(20) 暴力(5) 最短路(5) 未归档(5) 标记处理(1) 栈(1) 概率论(1) 模拟(2) 浮点数(1) 生成树(4) 算法(5) 素数筛(3) 线段树(6) 蓝桥杯(1) 计算几何(1) 贪心(26) 递推(3) 题解(3) 高精度(2)

/ 注册

全部文章 / 组合数学（共8篇）

E - NEQ(容斥原理&组合数学)

E - NEQ(容斥原理&组合数学) 传送门思路：容斥原理+组合数学。显然要求且数组中元素互异。所以对于数组，我们要从个数选个数来全排列。即个数为. 接下来我们考虑每个对于的方案，对于有多少个。显然这是个一个容斥原理的应用，我们考虑用总方案减去所有不合法的方案数，枚举不合法的位置...

2020-06-28

1 874

E - ∙ (Bullet)(组合数学）

E - ∙ (Bullet)(组合数学）传送门思路：显然对于一组只有两种情况，同号或者异号, 存在0。且要使。显然是同号与异号进行组合。且我们只需考虑除去最大公因数的组合. 因为。所以我们考虑储存同号的个数及对应异号的个数。(这里用实现即可）对于当前组，假设同号个数为,异号个数为，由...

组合数学

2020-05-18

1 750

k-size字符串(组合数学）

k-size字符串(组合数学）传送门思路：因为要分成段，显然字符与字符的段数绝对值值差设分成段，即： . 显然当为偶数时，只有这种情况。即或在个位置放置相应的一个字符或。接下来就等价于将个数放入个格子的方式. 也等价于整数分成个非负整数的方式。令为整数x分成个非负整数的方式。有(这...

组合数学

2020-05-18

1 855

C. Count Triangles(组合数学)

C. Count Triangles(组合数学) 传送门思路：考虑所有的组成的可行解。显然组成三角形, 因为，所以. 又因为.所以具有可行解的最小值为. 最大值即. 所以接下来考虑每种对答案的贡献,首先考虑对于当前,的取值。显然只能取.又因为.所以可选的个数为. 接下来考虑可选的个数. 根...

组合数学

2020-05-17

0 634

P2532 [AHOI2012]树屋阶梯（$Catalan$数&高精度）

P2532 [AHOI2012]树屋阶梯（数&高精度）题目传送门思路：卡特兰数的变形，可根据包含直角点的矩形覆盖的阶梯点的位置进行加法原理，然后对每个情况进行乘法原理，可以得到卡特兰数的递推式的形式。根据左上角阶梯的方案数右下角阶梯形的方案数该情况方案数由上图可知：图1为，图2为,图3...

Catalan

2020-05-12

0 714

费马小定理与逆元

费马小定理与逆元由费马小定理可知,（a/b)%c可以变换 1.如果c为质数,且b不是c的倍数 (注意这里不是b,c互质,因为c必须为质数，若b=5,c=6,b与c互质，但是结论不成立，比如：a=100,b=5,c=6 (100/5)%6=2,但（100*5^4)%6=4,显然不对) ...

2020-05-01

0 651

判断组合数奇偶性（组合数学）

判断组合数奇偶性（组合数学&位运算）结论：这里只将证明方法不做证明：证明方法：数学归纳法。先证几个较小的数满足结论，再假设C(n-1,k-1),C(n-1,k)满足结论，分四种情况讨论： pos1:C(n-1,k-1),C(n-1,k)都为偶数。 pos2:C(n-1,k-1),C(...

2020-05-01

0 755

ABC 162 D - RGB Triplets （组合数学）

ABC 162 D - RGB Triplets （组合数学）题目传送门思路： AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+5; typedef long long ll; char s...

2020-05-01

0 614