shyyhs

题解

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

/ 注册

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

选择困难症来自专栏

教我***儿子做题.https://www.acwing.com/problem/content/173/ 这个题的思路和这个题目是类似的.我们可以先进行排序,预处理k/2的种类存入一个数组..然后另外一半再进行dfs.这种做法很优但是对于这个题目来说.因为数据水,就不至于,但是还是写下. #inc...

dfs

2020-07-11

6 719

天码来自专栏

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

容斥原理

2020-07-11

1 738

守卫者的挑战来自专栏

今天更完这题结束吧,明天多校爆零ε唉.(这题和前面3个题目.然后打多校的时候,每天更一篇就好了...4天结束数论.这题是个概率题,很简单的maybe.题目意思啥的都不解释了.直接上代码: #include <bits/stdc++.h> using namespace std; cons...

dp

2020-07-11

2 737

错排&排列计数题解来自专栏

不要我为啥更这题,因为这种题,代码简单,思路简单.dp:先讲讲错排公式,D[1]=0,D[2]=1.这个是初始值.下面讲讲转移方程:D[i]=(n-1)*(D[i-1]+D[i-2]).考虑把第n个元素放到任意一个地方,那就有n-1种放法,假定我放的位子为k,那么我k就有两种放法,第一种是放到n的位...

dp 组合数学

2020-07-10

2 671

233矩阵&教大家推矩阵(开玩笑来自专栏

今天带大家推一个简单的矩阵快速幂?教大家推比fbi难一点的矩阵...首先看a[i][j]=a[i-1][j]+a[i][j-1].其中n行(n<=10)m列(m<=1e9).我们可以观察到n很小对吧.这个题目是已知矩阵第一行的所有数都长23、233、2333这样.矩阵的第一列已经给出,那...

矩阵快速幂

2020-07-10

3 770

线性基的简单贪心证明&新NIM游戏题解来自专栏

异或线性基是一个集合可以通过异或表示原集合的所有数.线性基的贪心证明正确性(简要),假定1,4,5.我们可以选择插入1,4|1,5,显然插入4,5更优.简单的更下这个题题解.我们知道原nim游戏,假如堆数异或和为0且你现在动,那么你必输.我如何才能使得到这个东西呢?换句话来说,我们制造一个别人通过取...

线性基高斯消元

2020-07-09

2 693

矩阵幂求和来自专栏

水题不解释.https://www.acwing.com/problem/content/99/做法相同不过换成了矩阵. #include <bits/stdc++.h> using namespace std; const int N=35; int n,m; struct vv{ ...

dfs 矩阵快速幂

2020-07-06

3 699

计算器来自专栏

有注释 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll x,y; void exgcd(ll a,ll b) { if(b==0) { x=1,y=0; ...

BSGS exgcd 快速幂

2020-07-06

2 643

阿九大战朱最学来自专栏

这个题目可能就是带了描述的中国剩余定理了吧?是不是越学越***？ //ex_gcd解ax+by=gcd(a,b).其中a,b必须互质,显然当x=1,y=0是一组解. #include <bits/stdc++.h> using namespace std; typedef long lo...

中国剩余定理

2020-07-06

2 759

青蛙的约会来自专栏

这题为啥评分"困难"?水的一批.题目描述:设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y.青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同.纬度线总长L米.现在要你求出它们跳了几次以后才会碰面.我们可以很简单的列出方程,假定跳t次会相遇. x+m*t=y+n*t+k*l...

exgcd

2020-07-04

1 570