shyyhs

分类

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

/ 注册

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

415篇文章 3901人学习

AtCoder思维大提升

6篇文章 753人学习

kuangbin专题记录

0篇文章 0人学习

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

19篇文章 848人学习

全部文章（共469篇）

破译密码来自专栏

这个题目和莫比乌斯反演并没有太大关系,只是用了莫比乌斯函数而已,本质就是整数分块+容斥原理.题目很简单:对于给定的整数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 719

Devu和鲜花来自专栏

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

容斥原理组合数

2020-06-30

2 1004

古代猪文来自专栏

这题就是个组合数而已hh..C(n,m)=C(n,n-m).然后就是最多sqrt(n)解决吧~还是水题舒服. #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=99991165...

中国剩余定理组合数

2020-06-30

2 762

计数交换来自专栏

这道题怎么可能简单--acwing评分乱搞啊...首先得知道,把一个环拆成n个自环需要n-1步.然后把一个奇数环拆成两种不同的环x,y的方案数为n,把一个偶数环拆成x==y方案数为n/2,其他都是n.进一步打表可知结论,把一个大小为n的环拆成n个大小为1的自环可行种数为f[n]=n^(n-2).然后...

计数

2020-06-28

2 604

acwing 210题解来自专栏

emm,线性基思想+高斯消元即可解决,其实高斯消元可以替代线性基(bolun).具体就是把你要异或的数全部进行二进制处理,假如那一位没有主元,且我这个值的最高位为1,因为每次我都会拿最高位消去其他位的1,那么我拿这个值当主元,消掉其他位子的1.emm消元完成后就是查询了,显然这个异或值可以看成一个二...

线性基高斯消元

2020-06-27

2 754

acwing 211题解来自专栏

这个是个很简单的水题,我就不解释了. #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e4+7; ll qp(ll a,ll b)//求a^b { a%=mod; ...

快速幂组合数

2020-06-27

2 633

装备购买题解=-= 来自专栏

emm这个题目说实话,假如没人指点就会很难,比如说我,,,自己看了很久没看懂,我首先读了个假题就去群里问,真tm弱智QAQ.这题假如你真懂高斯消元就会简单很多.我先带大家回顾下高斯消元..高斯消元是用来解多元一次方程组,然后可能这个方程可以用另外一个方程表示,那么我这个一次方程是不是就没有了意义?然...

线性基高斯消元

2020-06-26

3 656

中国剩余定理(非互质求法) 来自专栏

越更越慢,虽然很大一部分是因为智商的问题..我真的太菜了,,没办法ε=(´ο｀*)))唉..这个题目https://www.acwing.com/problem/content/description/1300/ emm理解了就不难,但是还是有点思维吧?怎么写呢?这个题意和上个基本一样,唯一不一样的...

中国剩余定理

2020-06-24

2 1225

中国剩余定理模板&ex_gcd回顾来自专栏

说句实话..学的不快,但是忘是忘的快..为什么要回顾ex_gcd呢?因为中国剩余定理要用逆元hh,所以我们要用ex_gcd求下数的逆元~我先把ex_gcd敲一下.. #include <bits/stdc++.h> using namespace std; int x,y;//解这个 a...

中国剩余定理

2020-06-24

3 736

acwing 274. 移动服务题解来自专栏

看着数据范围直接dp即可,注意题意 #include <bits/stdc++.h> using namespace std; const int N=205; const int M=1005; int dp[M][N][N];//有个人到了第i个指命位子,另外两个分别在j k位子的最...

dp

2020-06-22

3 672