shyyhs

分类

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3897人学习

AtCoder思维大提升

6篇文章 750人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 840人学习

全部文章（共9篇）

[SCOI2010]幸运数字来自专栏

思路本来以为是数位,想不出状态,后来又想着容斥一下以为都是的倍数的数量+的数量-的数量,然后就死了.万万没想到是. 思路很简单,就是先爆搜出那些合法的数/基数,其他数一定是这些数的倍数,然后把爆搜的数去个重,有些数是里面数的倍数,然后从小到大排序一下(剪枝).然后再用容斥原理统计答案即可. 坑点 ...

dfs 容斥原理

2021-03-22

3 835

Coprime Subsequences 来自专栏

题目: 问你有多少子序列gcd为1. 思路: gcd为的数,是不是等于都包含因子的个数-包含因子的个数-包含因子的个数-包含因子5的个数+包含因子的个数...这样容斥一下.其实就是一个莫比乌斯函数.包含因子的个数的子序列,假设因子是个,那么方案数是不是.选/不选-全不选. 代码: #include ...

容斥原理

2021-02-24

2 651

魔改森林来自专栏

前言: 很久很久以前就看到这个题目.记得这题应该是小乔出的.当时我队友来问我,我跟他讲了一下35分的做法.因为那个时候太菜了,不会容斥原理. 思路: 这题前面1000个数据直接dp即可.后面1e5,直接组合数预处理+容斥原理即可. 代码: #include <bits/stdc++.h>...

容斥原理 dp 组合数学

2021-01-27

3 829

Paint Box 来自专栏

一直不是很懂容斥原理的原因,学二分图的时候再看看!我们很容易知道,求给n个位子上色,可以最多使用k种颜色的方案数是.由容斥原理想到可以把最多->等于.那么就是最多使用k种颜色-最多使用k-1种颜色+最多使用k-2种颜***r>那么直接这样做就好了.(值得注意的是:因为取模了,所以会存在负...

容斥原理组合数学

2021-01-21

1 692

[HAOI2008]硬币购物来自专栏

讲真的看到题,我都没想容斥原理...是我太菜了吗.首先拿个完全背包进行预处理.然后我们来观察下完全背包的含义.什么含义呢,就是你每个物品都任意取,在容量为x的情况下的方案数.假定我们对于其中的一个做出了限制,那么方案数会不会减少呢>?显然是会的,因为有限制嘛~会减少多少呢...其实假设我们只能...

容斥原理 DP

2020-09-24

4 683

最后的晚餐(dinner) 来自专栏

首先因为是个环,我们得先随机分配一个确定起点,然后剩下的方案总数是(2*n-1)!.然后就是我们的容斥原理了,0个相邻的-1个相邻的+2个相邻的-3+4... 0个相邻的答案就是(2*n-1)! 1个相邻的答案是2*C(n,1)*(2*n-2)!.对于这个的解释就是你n对中选取1对,然后前后顺序考虑...

容斥原理

2020-09-22

9 1112

天码来自专栏

这题不难,重要是理解吧..我发现自己越来越菜了.求任意四个gcd为1,并不好求,但是它的对立面就很明显了,就是有相同的约数.那么我们就可以分解每个数的约数,显然这是一个莫比乌斯函数.又或者说莫比乌斯函数和容斥关系很大,对于总的方案数挺显然就是C(n,4).对于每个数,我们先进行质因数分解,然后进行合...

容斥原理

2020-07-11

1 735

破译密码来自专栏

这个题目和莫比乌斯反演并没有太大关系,只是用了莫比乌斯函数而已,本质就是整数分块+容斥原理.题目很简单:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d.这个怎么做呢?我们转化一下,就变成了x'=a/d,y'=b/d.并且gcd(x',y'...

莫比乌斯反演整数分块容斥原理

2020-07-01

2 713

Devu和鲜花来自专栏

这题想清楚就不难了hh,下面讲讲思路.题目:给你n堆花的数量ai,要你从n堆花里选取m朵.问你有多少种选法?(这样当然不能重复hh).怎么想呢?假设没有我们把m朵花铺平,且加n个隔板.总方案数是多少?显然C(n+m,n).不合法的方案数是多少?这个就要用容斥原理了,C(n+m-(ai+1),n).很...

容斥原理组合数

2020-06-30

2 999