4 zipper112

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 17w+

费马小定理&欧拉定理&扩展欧拉定理(欧拉降幂)

费马小定理定理:若ppp为质数且ppp和aaa互质那么就有ap−1≡1(mod  p)a^{p - 1}\equiv1(\mod p)ap−1≡1(modp)证明:ap=(a−1+1)pa^p = (a - 1 + 1)^pap=(a−1+1)p然后二项式展开ap=(a−1)p+Cp1(a−1)p−1+...+1a^p = (a - 1)^p + C_{p}^1(a - 1)^{p -1} + ...+1ap=(a−1)p+Cp1​(a−1)p−1+...+1由于Cpi=p!i!(p−i)!,

2020-08-04 17:07:26

Python--类属性,实例属性,类方法,静态方法

类属性&实例属性类属性类属性属于所有对象共有的,也就是所有对象都会使用同一个类属性,类属性定义在类的内部。类属性可以直接通过类名调用,修改类属性则所有对象使用时就都会改变。class Student: name = 'chiruno'#类属性 height = 1.56obj1 = Student()# 实例对象obj2 = Student()print(obj1.height)# 通过实例调用类属性print(obj2.height)Student.heigh

2020-08-02 10:41:31

F Fraction Construction Problem

题意:给两个数a,b求另外四个数c,d,e,f满足cd−ef=ab\frac{c}{d} - \frac{e}{f} = \frac{a}{b}dc​−fe​=ba​d < b and f < b1≤c,e≤4×10121≤c,e≤4×10^{12}1≤c,e≤4×1012如果不存在就输出-1 -1 -1 -1思路:看了题解之后来写一下思路,当时做一个笔记。...

2020-07-25 09:43:20

置换(群)&(J Just Shuffle)

牛客上多校第二场的J题,下来补的时候发现要置换群,于是就来学了,然后就想着记个笔记。置换(群)置换先说置换是啥对于一个n个元素集合S={a1,a2...an}S = \{a_1,a_2...a_n\}S={a1​,a2​...an​},排列P={p1,p2...pn}P = \{p_1,p_2...p_n\}P={p1​,p2​...pn​},将排列P每个元素当做S的下标替换掉原本S每个元素的位置,就得到一个置换f={ap1,ap2...apn}f = \{a_{p_1},a_{p_2}...a_{

2020-07-20 23:05:32

Python-列表推导式&生成器

列表推导式格式:list1 = [生成元素的表达式 for 原列表的元素 in 原列表 if 需要满足的条件]使用:以下面代码为例子,可以看到最终的list1里存了所有list0中的偶数元素的平方。其运行的过程是,从list0中挨个取出元素存在变量i,然后判断i是否被2整除,如果被整除就执行最开始的表达式,即i * i,然后把这个元素放到新的列表中可以看做,列表推导式就是从旧的列表之中推出新的列表list0 = [2, 5, 6, 7, 4]list1 = [i * i for i in

2020-07-19 11:48:53

模拟哈希表&字符串哈希

模拟哈希表引入哈希表就是根据一个关键值key进行高效访问的数据结构,可以通过哈希函数把一个数据当做key进行映射得到一个储存地址从而进行访问。比如想要查询100个数字范围在(1 ~ 1e8),查询它们是否有重复的值,那么就可以用哈希表来解决这个问题。对于小的数字我们就会习惯的会去一个数组进行标记,但是对于大的数字,开一个很大数组用来标记是很浪费空间,而且要处理的数只有100个,开一个1e8的数组实在是划不来,而且当数据再增大时,对于C++可能就无法直接开出这样的数组。哈希函数此时就可以对此些数字

2020-07-17 16:25:36

二分图最大匹配(匈牙利算法&Dinic算法)

二分图最大匹配:给出一个二分图,左边有若干个节点,右边有若干个节点,左边的节点想到匹配右边的节点,每个左边的节点每个都有若干个可以选择的对象,每个左边节点只能选择一个右边节点,每个右边节点也只能被选择一次。现在问你左边的节点能完成匹配的做多能有几个?通俗一点就是,有一群人,有一堆奖品,每个人都有自己心仪的奖品,每种奖品只有一份,问你最多能有多少能拿到自己心仪的奖品(每个人只能拿一份,而且每个人可能有多重心仪的奖品)?匈牙利算法:匈牙利算法的做法就是,先让每个左边节点去匹配,如果存在没有被匹配到的右边

2020-07-16 15:52:10

最小割&费用流

最小割:对于一个网络流图,把整张图分割成两个部分,一部分包含源点,一部分包含汇点的分割方式叫做割。割的容量即切割边时所切去边的容量之和,其中使割的容量最小的割叫做最小割求法:一张网络流图的最小割等于它的最大流,至于怎么证明可以看一下这篇博客这里本人太菜就不证明了。既然知道了它们相等,那么就可以跑最大流的模板来找最小割了常见模型:小M的作物上面有一道题,里面就用到了一个最小割的模型,即二选一模型。这种模型大概就是,有一些点集可以被分到连个集合中,分到A花费为XXX,分到B花费为XXX。费用

2020-07-16 15:23:48

网络流-最大流(Ford-Fulkerson算法&Dinic算法)

#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 1e5 + 5;int n,m,cnt = 2,h[maxn];int st,ed;bool vis[maxn];struct node{int w,e,nex;}e[maxn * 2];void add(int a,int b,int c){e[cnt].e = b;e[cnt].nex = h[a];e[

2020-07-14 10:13:34

Python--lambda表达式

lambda表达式就是一种函数,可以说是匿名函数。格式:lambda 参数1,参数2..参数n:表达式例子:fun1 = lambda a, b: a * bfun2 = lambda *args: args[0]fun3 = lambda a: a + 1 if a % 2 == 0 else a - 1fun4 = lambda x, y: print("这里:{}".format(x + y))print(fun1(3, 4))print(fun2(5, 4, 3))print(

2020-07-07 22:15:09

Dance Links(板子)

struct DLX{ int n, m, cnt; int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; int H[MAXM], S[MAXM]; int ansd; void init(int _n, int _m){ n = _n; m = _m; for (int i = 0; i <= m;

2020-07-07 09:16:36

Python-闭包&装饰器

闭包:闭包的格式:看下面一段代码def fun(a): b = 10 def inner_fun(): print(a + b) return inner_funx = fun(5)print(type(x))print(x)x()'''输出:<class 'function'><function fun.<locals>.inner_fun at 0x000001BB0CB02948>15'''

2020-07-04 21:38:45

双向BFS

作用双向BFS本质还是bfs,不过是在已知起点和终点的状况下从起点和终点两头开始bfs,这样可以节省时间避免单bfs时所带来的组合爆炸,而且在解决起点和终点均可移动且移动速度不同等鬼畜问题时有奇效模板#include<bits/stdc++.h>#define ll long longqueue<类型> qu[2];bool bfs(int id){ int s = qu[id].size();//每次只扩展当前这一层 while(s--){

2020-07-03 10:23:47

卡特兰数(笔记)

满足条件的01序列思路:由于前缀的0不能比1小也就说明了,前缀中sum(0)>sum(1)sum(0) > sum(1)sum(0)>sum(1)。实际生活中有很多这种问题,通常都是某个操作A是另一个操作B的前提,如果操作B的数目提前超过了操作A那么就不合法。对于这个问题其实是很有名的问题,它的解题思路非常清奇。把01序列看成两种操作,0表示向右走,1表示向上走(这里以n=3为例左下角为(1,1)右上角为(3,3))那么最终这个01序列可以看做从左下角走到右上角的的路径数目

2020-07-01 10:15:52

Numpy的基本操作(笔记)

这里记一下我看视频时所学到的东西作为一个笔记主要是为了学机器学习而做的基础准备,有错误的地方还大家请指出Numpy导入import numpy as npprint(np.__version__) # 查看版本数组的创建和属性创建lst = [1, 2, 3]arr = np.array(lst) # 通过传入列表创建一个np数组arr = np.zeros(shape=(5, 2), dtype=int)# 创建一个大小为5 X 2的int类型的0数组arr = np.ones(s

2020-06-30 23:37:11

[kuangbin带你飞]专题二 搜索进阶

A - Eight康托展开 + bfs题意:给你一个图形,由1,2,3…8和x构成,其中x可以与上下左右的方块相互交换位置,给出的一个图形,求把它通过最少的交换操作从而摆回指定位置的做法。思路:首先这道题有多组数据,如果每次都用bfs进行搜索绝对会爆时间。但是由于最终的状态相同,所以可以尝试倒着搜索,这样就只需要bfs一次。由于每次的状态都是一个矩阵所以不好标记。那么就需要对这些矩阵进行映射,把x设为0,那么矩阵就是由0-8这九个数字构成的排列。所以可以用康托展开来计算。代码#include

2020-06-30 09:49:46

容斥原理(笔记)

对于三个圆, S1,S2,S3他们如上图所示,现在要求求他们所构成图形的面积,该如何去求?这个问题很简单,S=S1+S2+S3−(S1∩S2)−(S1∩S3)−(S2∩S3)+(S1∩S2∩S3)S = S_1 + S_2 + S_3 - (S_1\cap S_2) - (S_1 \cap S_3) - (S_2 \cap S_3) + (S_1 \cap S_2 \cap S_3)S=S1​+S2​+S3​−(S1​∩S2​)−(S1​∩S3​)−(S2​∩S3​)+(S1​∩S2​∩S3​)如果换.

2020-06-30 08:26:00

状压dp

题目思路:可以枚举横着放小方块的情况,然后再枚举竖着放的情况

2020-06-29 11:20:57

康托展开&逆康托展开

用途康托展开是一种双射,用于排列和整数之间的映射,可用于排列的哈希康托展开公式:∑i=n1pi∗(i−1)!\sum\limits_{i = n}^{1} p_i*(i - 1)!i=n∑1​pi​∗(i−1)! 其中pip_ipi​为第iii个数构成的逆序的个数,n为排列数的个数例:排列:2134∑i=n1pi∗(i−1)!\sum\limits_{i = n}^{1} p_i*(i - 1)!i=n∑1​pi​∗(i−1)! = 3! * 1 + 2! * 0 + 1! * 0 + 0!

2020-06-20 17:58:27

求组合数

基本公式:Cnm=AnmAmm,Cnm=n!m!(n−m)!C_n^m = \frac{A_n^m}{A_m^m}, C_n^m = \frac{n!}{m!(n - m)!}Cnm​=Amm​Anm​​,Cnm​=m!(n−m)!n!​定义法:利用Cnm=n!m!(n−m)!C_n^m = \frac{n!}{m!(n - m)!}Cnm​=m!(n−m)!n!​来求,通常用于多次求在某一模下的组合数设inv[x]为x!的逆元则Cnm=n!m!(n−m)!=n!∗inv[n!]∗inv[(n−

2020-06-17 21:11:14

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。