shyyhs

题解

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

/ 注册

全部文章 / 题解（共329篇）

龙哥的问题来自专栏

这题思路清晰就好了.最大公约数即为因子,我们把n的因子求出来即可,然后根据欧拉的定理即是答案了.我们知道求gcd(1a,n)=i.就等同于gcd(1a/i,n/i)=1.然后就是统计答案了.代码如下: #include <bits/stdc++.h> using namespace st...

欧拉函数

2020-07-04

2 731

最大公约数来自专栏

求GCD(x,y)为素数个数也就是求d*gcd(x',y')个数,其中gcd(x',y')=1.d是质数.我们考虑枚举d.因为0<x,y<=N,那么x',y'<=N/d.题目就变简单了,那么就是枚举每个质因子.然后用前缀统计下欧拉函数. #include <bits/stdc...

欧拉函数数学

2020-07-04

0 611

剪纸游戏来自专栏

博弈论可以到学校好好给学弟们讲讲hh.sg函数是博弈解题的一个工具,就拿今天这个题目当例子来说吧.题目描述:给定一张NM的矩形网格纸，两名玩家轮流行动。在每一次行动中，可以任选一张矩形网格纸，沿着某一行或某一列的格线，把它剪成两部分。首先剪出1*1的格纸的玩家获胜。两名玩家都采取最优策略行动，求先手...

博弈论

2020-07-03

1 838

绿豆蛙的归宿来自专栏

dfs不解释. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; struct vv{ int to; double w; }; vector<vv>v[N]; double f[N...

期望 DFS

2020-07-02

0 574

扑克牌题解. 来自专栏

说句实话,假如不认真再想想期望就是平均数,你会对期望很迷惑.因为dfs是从后往前的,我们要求的答案是dp[0][0][0][0][4][4]当成答案,我们考虑用后面状态来更新前面状态.对于普通的4种花色来说,假设我们现在的状态是dp[a][b][c][d][x][y].那么我们从什么转移到它呢?显然...

期望 DFS DP

2020-07-02

0 664

Rainbow的信号来自专栏

大家画图自己领会,反正就是位运算. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],last[2],c1,c2,n; double ans_xor=0.0,ans_and=0.0,ans_...

期望位运算

2020-07-02

2 604

破译密码来自专栏

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

Devu和鲜花来自专栏

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

容斥原理组合数

2020-06-30

2 1010

古代猪文来自专栏

这题就是个组合数而已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 768

计数交换来自专栏

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

计数

2020-06-28

2 610