Day24h

分类

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章（共6篇）

Co-prime

B - Co-prime 参考：HDU 4135 Co-prime (容斥原理) 这个题利用的是容斥原理，同时也利用到了求质数个数的一个技巧—— 1~m 内与 n 不互质的个数为 m/n 个： prime.clear(); for(ll i=2;i*i<=n;++i) ...

容斥原理二进制质数

2019-08-10

0 359

Color

C - Color 参考：CF GYM 100548 Color（2014ACM西安现场赛Problem F） Codeforces Gym 100548F Color (组合数＋容斥) 思路：可以参考第一个博客的思路，很容易理解需要注意的地方：因为数据很大所以一不...

容斥原理组合数逆元

2019-08-11

0 388

Tree

Tree 参考 xk 老哥的博客：POJ 1741 Tree 点分治找重心： void getrt(int fa,int u,int num) //num指的是这个节点的子树中有多少个节点 { siz[u]=1; int maxnum=0; ...

点分治重心容斥原理

2019-08-14

0 410

Number Of Permutations

Number Of Permutations 思路：利用容斥，首先所有可能的排列肯定是fac[n]，然后可能会有三种 bad 的情况： ①第一个元素的排列是非递减 ②第二种是第二个元素的排列是非递减 ③这两个可能出现的重叠情况，意思就是说同时导致①②成立这个时候我们利用容斥...

容斥原理

2019-08-23

0 479

Another Filling the Grid

E. Another Filling the Grid 参考：Codeforces Round #589 (Div. 2)-E. Another Filling the Grid-容斥定理容斥这个东西可以理解，但是运用到实际的时候，还是觉得有点迷迷糊糊的，不知道套公式会不会是一...

容斥原理组合数快速幂

2019-10-04

0 359

Two Arrays

C. Two Arrays \(dp[i][j]\)表示有\(j\)个数每个数的范围为\(1～i\)时的非递减排列种数，因为 n 和 m 的数据范围也不大，用记忆化搜索很快可以得出每一个值。再来看满足条件时的\((a,b)\)，\(a\)为非递减序列，\(b\)为非递增序列，所以\(b...

记忆化搜索容斥原理 dp

2020-01-15

0 431