wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

网络流之二分图匹配【转】

二分图：　二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。——摘自百度百科二分图匹配： ...

2018-07-17

0 496

网络流之最大流

什么是网络流：　　　网络流就是给出一个图，然后每条边上有一个最大的流量(容量)，只有出流没有入流的点叫做源点，只有入流没有出流的点叫做汇点。残余网络：　　不断地给每条边分配流量，然后用其剩余的容量减去这些流量，得到残量，残量构成残余网络。增广路：　　在残余网络中，还可以继续分配流...

2018-07-12

0 500

网络流之最大流

什么是网络流：　　　网络流就是给出一个图，然后每条边上有一个最大的流量(容量)，只有出流没有入流的点叫做源点，只有入流没有出流的点叫做汇点。残余网络：　　不断地给每条边分配流量，然后用其剩余的容量减去这些流量，得到残量，残量构成残余网络。增广路：　　在残余网络中，还可以继续分配流...

2018-07-12

0 566

矩阵快速幂优化菲波那切数列

　　普通的斐波那契数列的递推式很简单，但是如果要求第1014个斐波那契数的话，肯定会tle，这时就可以用矩阵快速幂来优化。　　菲波那切数列普通的递推式是　　f[i]=f[i-1]+f[i-2] 　　而矩阵乘法的规则是，讲n行m列的矩阵与k行n列的矩阵相乘，所得矩阵的第i行第j列的数是由第一...

数论

2018-07-06

0 468

矩阵快速幂优化菲波那切数列

　　普通的斐波那契数列的递推式很简单，但是如果要求第1014个斐波那契数的话，肯定会tle，这时就可以用矩阵快速幂来优化。　　菲波那切数列普通的递推式是　　f[i]=f[i-1]+f[i-2] 　　而矩阵乘法的规则是，讲n行m列的矩阵与k行n列的矩阵相乘，所得矩阵的第i行第j列的数是由第一...

数论

2018-07-06

0 507

快速幂&快速乘法

尽管快速幂与快速乘法好像扯不上什么关系，但是东西不是很多，就一起整理到这里吧快速幂思想就是将ax看作x个a相乘，用now记录当前答案，然后将指数每次除以2，然后将当前答案平方，如果x的2进制最后一位为1的话，就将答案乘以现在的数。快速乘法类似，只是将a*x看作x个a相加。代码　　 ...

数论

2018-07-06

0 422

快速幂&快速乘法

尽管快速幂与快速乘法好像扯不上什么关系，但是东西不是很多，就一起整理到这里吧快速幂思想就是将ax看作x个a相乘，用now记录当前答案，然后将指数每次除以2，然后将当前答案平方，如果x的2进制最后一位为1的话，就将答案乘以现在的数。快速乘法类似，只是将a*x看作x个a相加。代码　　 ...

数论

2018-07-06

0 496

筛法

有两种筛法，第一种叫做埃拉托斯特尼筛法（复杂度O(n log logn)），另一种是欧拉筛法（复杂度O(n)）埃拉托斯特尼筛法其实就是用已得到质数，去将他的所有n以内倍数标记为合数，最后剩下的就是合数。在进行筛法的同时，可以顺便找到每个数的最小质因数（就是第一次更新他的那个质数）欧...

数论

2018-07-06

0 518

筛法

有两种筛法，第一种叫做埃拉托斯特尼筛法（复杂度O(n log logn)），另一种是欧拉筛法（复杂度O(n)）埃拉托斯特尼筛法其实就是用已得到质数，去将他的所有n以内倍数标记为合数，最后剩下的就是合数。在进行筛法的同时，可以顺便找到每个数的最小质因数（就是第一次更新他的那个质数）欧...

数论

2018-07-06

0 476

费马定理&欧拉定理

费马定理: ap≡a(mod p) 其中p为质数，且a不是p的倍数证明：。。。。。欧拉定理： aφ（p）≡1(mod p) φ（x）（欧拉函数）为小于等于x且与x互质的数的个数 φ（x）=∏（pi-1）*piki-1 其中pi表示 x的质因数，ki表示这种质因数的个数 ...

数论

2018-07-06

0 491