Scorpioch

分类

01分数规划(1) dp(4) gcd(2) NOIP膜你赛(1) OIer的刷题记录(25) poj(3) sgu(1) 【神奇的】模板(1) 二分(1) 动态规划 - 数位DP(1) 动态规划 - 概率DP(1) 动态规划 - 背包(2) 字符串 - KMP(1) 搜索(1) 数学(2) 数据结构 - 线段树(4) 数论(2) 未归档(72) 算法(1) 背包问题(1)

/ 注册

全部文章（共109篇）

【Codeforces2015ICL,Finals,Div. 1#J】Ceizenpok's formula（扩展Lucas定理+中国剩余定理）

题目链接：https://vjudge.net/problem/Gym-100633J 题解：扩展Lucas+中国剩余定理裸题，讲解在这里：传送门 #include <iostream> #include <cstdio> #include <cstring>...

2017-07-26

0 524

【模板】【POJ2891】扩展中国剩余定理

exCRT适用于模数两两不互素的情况，思路是把方程两两合并即可，具体看这个博客吧：传送门 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #i...

2017-07-26

0 407

【HDU3037】Saving Beans

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3037 题目大意：求在n棵树上摘不超过m颗豆子的方案，结果对p取模。题解：问题可以转化成求方程 <nobr> x1+x2+……+xn=k </nobr>的非...

2017-07-25

0 369

【数论】乘法逆元总结

前言：我们知道在模意义下的加减乘运算都是具有封闭性的，但除法确是例外，所以我们就要找一种在模意义下代替除法运算的东西想看代码的在最下方定义：如果有 <nobr> ab≡1(modp) </nobr>，则称b是mod p意义下a的乘法逆元。记...

2017-07-25

0 578

【数论】扩展欧几里得

欧几里得算法用于求解最大公因数主要原理： int gcd(int a,int b){return b?gcd(b,a%b):a;} 扩展欧几里得算法用于求解二元一次方程首先了解一下裴蜀定理： <nobr> ax+by=c </nobr>有解当且仅...

2017-07-25

0 547

【数论】埃氏筛

复杂度 <nobr> O(nloglogn) </nobr> 证明的话思路是用素数分布定理列出表达式，然后定积分确定时间界（别问我怎么知道的QAQ，万能的知乎），贴个链接赶紧跑orz。实际上已经很接近 <nobr> O（n） &l...

2017-07-25

0 495

【数论】线性筛与积性函数

一篇总结很全面的blog： http://blog.csdn.net/tc_to_top/article/details/48025849 欧拉函数：定义： <nobr> φ(n) </nobr>表示1~n中和n互素的数目性质：首先可以根据...

2017-07-25

0 532

【模板】扩展kmp

扩展kmp用于求解模板串S的每一个后缀与串T的LCP，复杂度 <nobr> O(|S|+|T|) </nobr> next【i】表示串T【i~（lenT-1）】与串T的LCP（自身匹配） extend【i】表示S【i~（lenS-1）】与串T的LCP 通过...

2017-07-24

0 420

【uva1328】Period

题目链接：https://vjudge.net/problem/UVA-1328 题解： KMP i-next【i】为最小循环节每次判断能否除尽且不是它本身即可 #include<iostream> #include<cstdio> #include<cst...

2017-07-24

0 389

【uva11732】"strcmp()" Anyone?

题目链接：https://vjudge.net/problem/UVA-11732 题解：建一棵trie树，每次经过一个点，该点的计数器+1 插入的时候顺便统计，分字符相同（*2）和不同（*1）讨论一下就好注意最后一位的比较，可以都赋值为47（’\’）考虑到串只有4000个但串比较长...

2017-07-24

0 699