文章目录
  1. 1. 使用方法
  2. 2. 更新日志
  3. 3. 通用文件头
    1. 3.1. 纸农の标准库
    2. 3.2. 数学计算
    3. 3.3. 算法
  4. 4. 存储结构
    1. 4.1. 前向链表
  5. 5. 统计结构
    1. 5.1. 树状数组
    2. 5.2. 线段树
    3. 5.3. 稀疏表
  6. 6. 数论
    1. 6.1. 矩阵
    2. 6.2. 高精度正整数
    3. 6.3. 离散化
    4. 6.4. 欧拉筛法
    5. 6.5. 快速数论变换
  7. 7. 图论
    1. 7.1. 前向星
    2. 7.2. 强联通分量
    3. 7.3. 2-SAT
    4. 7.4. 网络流
  8. 8. 字符串
    1. 8.1. 马拉车算法
    2. 8.2. AC自动机
    3. 8.3. 后缀自动机
  9. 9. 其他
    1. 9.1. 珍爱生命,远离爆栈

不管你信不信,反正这个页面是炸了。
如果不及时补上,会产生一片虚空,继而演变成黑洞。
然后像抽水马桶一样,把整个博客吸进去。

使用方法

$Github$上有ReleaseDebug两种版本。作为头文件使用的,建议下载Release版本。

平时写代码的时候,可以通过#include <...>的方式,来调用这些功能。提交的时候,把这些文件的所有内容全选,然后替换掉include语句即可。因为我使用了ifndef进行检测,不会出现multi-define之类的蠢事,可以安心食用。

  • Dev-Cpp x64
    可以放入Dev-Cpp\MinGW64\lib\gcc\x86_64-w64-mingw32\4.8.1\include\c++
  • MinGW
    丢进MinGW\mingw32\lib\gcc\mingw32\4.8.1\include\c++
  • Eclipse 用户
    1. 新建一个C++ Project
    2. 在其中新建一个Source Folder
    3. 工程上右键Properties -> C/C++ General -> Paths and Symbols,
    4. 点击Includes 选项卡,在GNU C++中点Add
    5. Directory/工程名/文件夹名
    6. 勾上Is a workspace path,按OK即可
  • 其他用户
    你可以直接copy代码进去,其实姿势无甚影响。

ps. 不同版本的文件夹会有些许差异
pss. 建议以后写程序一直用这个工程,方便你管理源码,一如CodeWorld

更新日志

20151222: 升级至城堡时代(c++11)
20150912: 添加了matrix.h
20150911: 添加了anti-stackoverflow.h,解决了g++爆栈问题
20150904: 修改了sparse的运行机制,添加了两个二元运算符
20150822: 添加了discrete离散化模块
20150821: 添加了csl_algo中的euler函数
20150820: 删除了csl_math中的冗余内容
20150815: 你以为我真的会写?
20150503: 今后代码将直接与GitHub同步
20150503: 更新了bigint.h、fenwick.h
20150428: 更新了csl_math.h
20150427: 更新了csl_std.h

通用文件头

纸农の标准库

csl_std_intro.cppview raw
1
2
3
4
5
6
/*
* 20150808L
*
* 直接把csl_std.h的内容作为.cpp文件生成的模板
*
*/

csl_std.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Name : ChouUn's Standard Library 纸农の标准库
// Copyright : fateud.com
#ifndef CSL_STD_H_
#define CSL_STD_H_ 20151122L
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<pii> vpii;

template<class T1, class T2>
inline std::istream& operator >> (std::istream& in, std::pair<T1,T2>& a)
{ return in >> a.first >> a.second; }

#define rep(i,a,b) for(auto i=a,i##_n=b;i<i##_n;++i)
#define per(i,a,b) for(auto i=b,i##_n=a;i-->i##_n;)

#endif /* CSL_STD_H_ */

数学计算

csl_math_intro.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
* 20151008L
*
* template <typename _Tp>
* gcd(_Tp a, _Tp b) : _Tp
* 返回 a 和 b 的最大公约数
*
* template <typename _Tp>
* gcd(_Tp a, _Tp b, _Tp& x, _Tp& y) : _Tp
* 返回 a 和 b 的最大公约数, 且满足 ax + by = 1
*
* template <typename _Tp>
* lcm(_Tp a, _Tp b) : _Tp
* 返回 a 和 b 的最小公倍数
*
* template <typename _Tp, typename _Key>
* pow(_Tp c, _Tp n, _Key k) : _Tp
* 返回 c * (n ^ k)
*
* template <typename _Tp, typename _Key>
* pow(_Tp c, _Tp n, _Key k, _Tp m) : _Tp
* 返回 c * (n ^ k) % m
*
* template <typename _Tp>
* inv(_Tp x, _Tp m) : _Tp
* 返回 x 对于模数 m 的逆元, m 是质数
*
*/

csl_math.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// Name : Mathematical Computation 数学计算
// Copyright : fateud.com

#ifndef CSL_MATH_H_
#define CSL_MATH_H_ 20160313L

#include <cmath>
#include <functional>
#include <vector>

#ifndef M_PI
#define M_E 2.71828182845904523536 // - e
#define M_LOG2E 1.44269504088896340736 // - log2(e)
#define M_LOG10E 0.434294481903251827651 // - log10(e)
#define M_LN2 0.693147180559945309417 // - ln(2)
#define M_LN10 2.30258509299404568402 // - ln(10)
#define M_PI 3.14159265358979323846 // - pi
#define M_1_PI 0.318309886183790671538 // - 1/pi
#define M_SQRT2 1.41421356237309504880 // - sqrt(2)
#define M_SQRT1_2 0.707106781186547524401 // - 1/sqrt(2)
#endif /* M_PI */

namespace csl {
/*
* greatest common divisor
*/

template <typename T>
inline T gcd(T a, T b) {
for(T c = T(); !!b;)
c = a % b, a = std::move(b), b = std::move(c);
return a;
}
/*
* extended Euclidean algorithm
* solve ax + by = gcd(a,b)
*/

template <typename T>
T gcd(const T& a, const T& b, T& x, T& y) {
if(!b) return x = 1, y = 0, a;
T r = gcd(b, a % b, y, x);
return y = y - a / b * x, r;
}

/**
* least common multiple
*/

template <typename T>
inline T lcm(const T& a, const T& b) {
return a / gcd(a, b) * b;
}

/**
* divide and conquer algorithms (with modulo operation)
*/

template <typename V, typename K, typename M, typename F1, typename F2>
inline V dnc(V c, V n, K k, M m, const F1& op1, const F2& op2) {
for(n = op2(n, m); !!k; n = op2(op1(n, n), m), k >>= 1)
if(k & 1) c = op2(op1(c, n), m);
return c;
}

/**
* divide and conquer algorithms
*/

template <typename V, typename K, typename F>
inline V dnc(V c, V n, K k, const F& op) {
for(; k; n = op(n, n), k >>= 1)
if(k & 1) c = op(c, n);
return c;
}

/**
* return a * b (mod m)
*/

template <typename V>
inline V mul(V a, V b, const V m) {
return dnc(V(), a, b, m, std::plus<V>(), std::modulus<V>());
}

/**
* return c * n ^ k
*/

template <typename V, typename K>
inline V pow(V c, V n, const K k) {
return dnc(c, n, k, std::multiplies<V>());
}

/**
* return c * n ^ k (mod m)
*/

template <typename V, typename K>
inline V pow(V c, V n, const K k, V m) {
return dnc(c, n, k, m, std::multiplies<V>(), std::modulus<V>());
}

/**
* return 1 / x (mod m)
*/

template <typename V>
inline V inv(const V& x, const V& m) {
V p, q;
return gcd(x, m, p, q), (p % m + m) % m;
}

template <typename V>
inline std::vector<V> divide(V x) {
std::vector<V> res;
if (x % 2 == 0) { res.push_back(2); while (x % 2 == 0) x >>= 1; }
for (V i(3); i * i <= x; i += 2) {
if (x % i) continue;
res.push_back(i); while (x % i == 0) x /= i;
}
if (x != V(1)) res.push_back(x);
return res;
}

/**
* return Primitive Root of x about m
*/

template <typename V>
inline V root(const V& P) {
std::vector<V> p = csl::divide(P - 1);
for (V g = 2; g < P; ++g) {
bool flag = true;
for (auto i = p.begin(); i != p.end(); ++i)
if (csl::pow(V(1), g, (P - 1) / *i, P) == 1) { flag = false; break; }
if (flag) return g;
}
return -1;
}

} // namespace csl

#endif /* CSL_MATH_H_ */

算法

csl_algo_intro.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
* 20150917L
*
* template <typename _Tp>
* struct less : public std::binary_function<_Tp, _Tp, _Tp>
* 返回较小值
*
* template <typename _Tp>
* struct greater : public std::binary_function<_Tp, _Tp, _Tp>
* 返回较大值
*
* namespace euler
* 欧拉函数
*
* euler::phi : std::vector<int>
* 获取欧拉函数
*
* euler::div : std::vector<int>
* 获取最小因子
*
* euler::prm : std::vector<int>
* 获得素数序列
*
* euler::build(int __n) : void
* 欧拉筛法, [0,__n)
* 初始化欧拉函数/最小因子/素数序列
*
* template <typename _Tp, typename _Comp >
* isomorph_min(_Tp* data, std::size_t size, _Comp comp) : std::size_t
* 给定从 data 起长为 size 循环两次的序列,求其最大/小同构中最小的下标
*
* template <typename _Tp, typename _Comp >
* isomorph_max(_Tp* data, std::size_t size, _Comp comp) : std::size_t
* 给定从 data 起长为 size 循环两次的序列,求其最大/小同构中最大的下标
*
*/

csl_algo.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
// Name : Algorithm 算法
// Copyright : fateud.com
#ifndef CSL_ALGO_H_
#define CSL_ALGO_H_ 20150917L
#include <cmath>
#include <vector>
namespace csl {
static double M_EPS = 1e-8;
/**
* the sign of x is positive or nagetive
* return -1 means less, 0 means equal, 1 means greater
*/

inline int sgn(double x) {
return std::fabs(x) < M_EPS ? 0 : (x < 0 ? -1 : 1);
}
/**
* compare between double a and double b
* return -1 means less, 0 means equal, 1 means greater
*/

inline int cmp(double a,double b) {
return sgn(a - b);
}

/**
* return the minimum between double x and y
*/

template<typename _Tp>
struct min {
const _Tp& operator ()(const _Tp& x,const _Tp& y) const {
return x < y ? x : y;
}
};
/**
* return the maximum between double x and y
*/

template<typename _Tp>
struct max {
const _Tp& operator ()(const _Tp& x,const _Tp& y) const {
return x > y ? x : y;
}
};

/**
* calc the lowest factor of number (with prime & phi & mu)
*/

namespace prime {
std::vector<int> mu;
std::vector<std::size_t> phi, div, prm;
void build(std::size_t n) {
mu.assign(n, 0), mu[1] = 1, phi.assign(n, 0), phi[1] = 1;
div.assign(n, 0), prm.clear(), prm.reserve(n >> 3);
for(std::size_t i = 2; i < n; ++i) {
if(!div[i]) mu[i] = -1, phi[i] = i - 1, div[i] = i, prm.push_back(i);
for(std::size_t j = 0, m = prm.size(), k; j < m; ++j) {
if((double)i * prm[j] >= n) break;
div[k = i * prm[j]] = prm[j];
if(i % prm[j] == 0) {
phi[k] = phi[i] * prm[j], mu[k] = 0;
break;
}
else mu[k] = -mu[i], phi[k] = phi[i] * (prm[j] - 1);
}
}
}
} // namespace prime

/**
* minimum isomorphic representation of string
*/

template<typename _Tp,typename _Comp>
std::size_t isomorph_min(_Tp data[],std::size_t size,_Comp comp) {
std::size_t i = 0, j = 1;
for(std::size_t k; i < size && j < size;) {
for(k = 0; data[i + k] == data[j + k] && k < size; ++k)
;
if(k == size) return i;
if(comp(data[j + k], data[i + k])) std::swap(i, j);
j = std::max(j + k + 1, i + 1);
}
return i;
}
/**
* maximum isomorphic representation of string
*/

template<typename _Tp,typename _Comp>
std::size_t isomorph_max(_Tp data[],std::size_t size,_Comp comp) {
std::size_t i = 0, j = 1;
for(std::size_t k, p = -1; i < size && j < size;) {
for(k = 0; data[i + k] == data[j + k] && k < size; ++k)
;
if(k == size) {
i = std::max(i, j);
if(~p) for(p = i - p; i + p < size; i = i + p)
;
j = i + 1, p = i;
}
else {
if(comp(data[j + k], data[i + k])) std::swap(i, j);
j = std::max(j + k + 1, i + 1);
}
}
return i;
}

} // namespace csl
#endif /* CSL_ALGO_H_ */

存储结构

前向链表

挖坑重写

统计结构

树状数组

fenwick_intro.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
* 20150823L
*
* struct fenwick_tree
*
* 模板参数:
* fenwick_tree < _Tp, _Op = std::plus<_Tp> >
* _Tp : 限定元素类型
* _Op : 限定元素运算
*
* 成员变量:
* m_data : std::vector<_Tp>
* 存储空间
* m_func : _Op
* 运算仿函数
*
* 职能:
* build(value_type* p_data, size_type p_size) : void
* 以p_data为源数据地址, p_size为元素数量, 建立树状数组
*
* build(size_type p_size) : void
* 以p_size为元素数量, 建立空树状数组
*
* 元素访问:
* query(size_type __x, value_type __res = value_type()) : value_type
* 获得前__x个元素的统计, 以__res为底
*
* 修改符:
* update(size_type __x, value_type __v) : void
* 第__x个元素的值修改__v
*
*/

fenwick.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Name : Fenwick Tree 树状数组
// AKA : Binary Indexed Tree 二分索引树
// Copyright : fateud.com

#ifndef FENWICK_H_
#define FENWICK_H_ 20150928L

#include <vector>
#include <functional>

#ifndef lowbit
#define lowbit(x) ((x)&-(x))
#endif

namespace csl {
template<typename _Tp,typename _Op = std::plus<_Tp>>
struct fenwick_tree {
typedef _Tp value_type;
typedef std::size_t size_type;
std::vector<value_type> data;
fenwick_tree() : func() {}
inline void build(size_type p_size)
{ data.assign(p_size + 1, 0); }

void build(const value_type* p_data, size_type p_size) {
data.resize(p_size + 1);
for(int i = 1; i <= p_size; ++i) data[i] = p_data[i - 1];
for(int i = 1, j; i <= p_size; ++i)
if((j = i + lowbit(i)) <= p_size) data[j] = func(data[j], data[i]);
}
inline size_type size() const
{ return data.size(); }

value_type query(size_type __x, value_type __res = value_type()) const {
for(; __x > 0; __x -= lowbit(__x)) __res = func(__res, data[__x]);
return __res;
}
void update(size_type __x,const value_type& __v)
{ for(; __x < data.size(); __x += lowbit(__x)) data[__x] = func(data[__x], __v); }

private:
const _Op func;
};

std::size_t search(fenwick_tree<int>& f,int x) {
if(f.query(f.size() - 1) < x) return -1;
std::size_t res = 0;
for(int i = 1 << 20; i > 0 && x > 0; i >>= 1) {
if(res + i >= f.size()) continue;
if(x <= f.data[res + i]) continue;
x -= f.data[res += i];
}
return res + 1;
}

} // namespace csl

#endif /* FENWICK_H_ */
fenwick_exam.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//@ Including Header
#include <csl_std.h>
#include <fenwick.h>

/*
* Name : fenwick_exam.cpp
* Date : 2015年5月5日 下午7:51:37
* Copyright : fateud.com
*/


//@ Main Function
int main() {
csl::fenwick_tree<int> ft;
ft.build(6);
ft.update(1, +3); // 第1个元素增加3 : +3 +0 +0 +0 +0 +0
ft.update(2, -5); // 第2个元素减少5 : +3 -5 +0 +0 +0 +0
printf("sum of [1,2] = %d\n", ft.query(2));
ft.update(6, +1); // 第6个元素增加1 : +0 +0 +0 +0 +0 +1
ft.update(2, -4); // 第2个元素减少4 : +0 -4 +0 +0 +0 +1
printf("sum of [1,6] = %d\n", ft.query(6));
return 0;
}

线段树

稀疏表

sparse_intro.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
* 20150904L
*
* 模板参数:
* sparse_table <_Tp, _Compare>
* _Tp : 限定元素类型
* _Compare : 比较函数
*
* 成员变量:
* m_data : vector< vector<_Tp> >
* 存储空间
*
* m_comp : _Compare
* 比较函数实例
*
* 职能:
* clear() : void
* 清空存储空间
*
* 元素访问:
* query(size_t first, size_t last) const : _Tp
* 查询区间[first,last]的最值
*
* 修改符:
* build(_Tp* p_data, size_t p_size) : void
* 以p_data为源数据地址, p_size为元素数量
*
*/

sparse.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Name : Sparse Table 稀疏表
// Copyright : fateud.com
#ifndef SPARSE_H_
#define SPARSE_H_ 20151124L
#include <vector>
using std::size_t;

#ifndef CSL_ALGO_H_
#pragma message("need : csl_algo.h");
#include <csl_algo.h>
#endif

namespace csl {
static std::vector<std::size_t> msb(2, 0);
void msb_build(std::size_t p_data) {
for(std::size_t i = msb.size(), t = msb[i - 1]; i <= p_data; ++i)
msb.push_back(t += !(i & (i - 1)));
}

template<typename T, typename F = csl::min<T>>
class sparse_table {
public:
sparse_table() :
data(), func() {
}

inline void clear() {
data.clear();
}

inline size_t size() const {
return data.empty() ? 0 : data.at(0).size();
}

inline T query(size_t first, size_t last) const {
size_t k = csl::msb[last-first+1];
return func(data[k][first], data[k][last+1-(1<<k)]);
}

void build(T* s, size_t n) {
msb_build(n), data.clear();
data.push_back(std::vector<T>(s, s+n));
for(size_t k = 1, d = 2, t = 1; d <= n; ++k, d <<= 1, t <<= 1) {
data.push_back(std::vector<T>(n-d+1));
for(size_t i = 0, j = n+1-d; i < j; ++i)
data[k][i] = func(data[k-1][i], data[k-1][i+t]);
}
}

private:
std::vector<std::vector<T>> data;
const F func;
};
} // namespace csl
#endif /* SPARSE_H_ */

数论

矩阵

matrix.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// Name : Matrix 矩阵
// Copyright : fateud.com
#ifndef MATRIX_H_
#define MATRIX_H_ 20151229L

#include <vector>
#include <iostream>

namespace csl {
template<typename T>
class matrix {
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;

typedef std::size_t size_type;

typedef matrix<T> _Self;

matrix() :
data(), h(), w() {
}

matrix(size_type h, size_type w) :
data(h * w), h(h), w(w) {
}

static _Self
identity(size_type n) {

_Self res(n, n);
for(size_type i = 0; i < n; ++i)
res[i][i] = value_type(1);
return std::move(res);
}

inline size_type
height() const {

return h;
}

inline size_type
width() const {

return w;
}

inline value_type*
operator [] (size_type x) {
return data.data() + x * w;
}

inline const value_type*
operator [] (size_type x) const {
return data.data() + x * w;
}

_Self&
operator *= (const _Self& b) {
_Self c(h, b.w);
for(size_type i = 0; i < h; ++i) {
for(size_type k = 0; k < w; ++k) {
value_type tmp = (*this)[i][k];
if(!tmp) continue;
for(size_type j = 0; j < b.w; ++j)
c[i][j] += tmp * b[k][j];
}
}
return (*this) = std::move(c);
}

_Self
operator * (const _Self& b) const {
return _Self(*this) *= b;
}

_Self&
operator += (const _Self& b) {
for(size_type i = 0, n = height() * width(); i < n; ++i)
data[i] += b.data[i];
return *this;
}

_Self
operator + (const _Self& b) const {
return _Self(*this) += b;
}

friend std::ostream&
operator << (std::ostream &os, const _Self& a) {
size_type n = a.height();
size_type m = a.width();
for(size_type i = 0; i < n; ++i) {
for(size_type j = 0; j < m; ++j)
os << a[i][j] << ' ';
os << '\n';
}
return os;
}

private:
std::vector<value_type> data;
size_type h, w;
};
} // namespace csl
#endif /* MATRIX_H_ */

高精度正整数

bigint.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
// Name : BigInt.h 大整数
// Copyright : fateud.com

#ifndef BIGINT_H_
#define BIGINT_H_ 20160312L

#include <vector>
#include <climits>
#include <iostream>

namespace csl {
#define long long long
class BigInt {
public:
typedef std::uint32_t uint;
typedef std::uint64_t ulong;
typedef std::vector< uint > container;
typedef BigInt _Self;

public:
static const int kcbitUint = 32;
static const uint kuMaskHighBit = (uint)INT_MIN;
static const int MultiplyThreshold = 32;

private:
int _sign;
container _bits;

public:
BigInt() :
_sign(0), _bits() {
}

BigInt(int value) {
if (value < 0)
_sign = -1, _bits = container(1, -value);
else if (value > 0)
_sign = +1, _bits = container(1, value);
else
_sign = 0, _bits = container();
}

BigInt(uint value) :
_sign(+1), _bits(1, value) {
}

BigInt(long value) {
if (INT_MIN <= value && value <= INT_MAX)
*this = _Self(int(value));
else {
ulong x = 0;
if (value < 0)
x = (ulong)-value, _sign = -1;
else
x = (ulong)value, _sign = +1;
if (x <= UINT_MAX)
_bits = container(1, x);
else
_bits = container(2), _bits[0] = x, _bits[1] = x >> kcbitUint;
}
}

BigInt(ulong value) {
_sign = +1;
if (value <= UINT_MAX)
_bits = container(1, value);
else
_bits = container(2), _bits[0] = value, _bits[1] = value >> kcbitUint;
}

BigInt(int n, const container& rgu) :
_sign(n), _bits(rgu) {
}

BigInt(const container& value, bool negative) {
StripLeadingZero(_bits = value);
_sign = !_bits.size() ? 0 : negative ? -1 : +1;
}

BigInt(container&& value, bool negative) {
StripLeadingZero(_bits = std::move(value));
_sign = !_bits.size() ? 0 : negative ? -1 : +1;
}

BigInt(const std::string& s) {
int n = s.size(), cur = 0;
if (s[cur] == '0')
_sign = 0, ++cur;
else if (s[cur] == '-')
_sign = -1, ++cur;
else
_sign = 1;

container base = container(1, 10);
_bits = container(1, 0);
while (cur < n) {
uint d = s[cur++] - '0';
container lb = container(_bits.size() + base.size());
std::swap(lb, _bits);
Multiply(lb.data(), lb.size(), base.data(), base.size(), data(), size());
container newBits = container(1, d);
if (d) AddSelf(data(), size(), newBits.data(), newBits.size());
StripLeadingZero(_bits);
}
}

public:
inline uint* data() {
return _bits.data();
}

inline const uint* data() const {
return _bits.data();
}

inline uint size() const {
return _bits.size();
}

inline std::string to_string() const {
return FormatBigInt(*this);
}

inline _Self abs() const {
return _Self(_sign < 0 ? -_sign : _sign, _bits);
}

inline friend std::istream& operator >>(std::istream& is, _Self& value) {
std::string s;
return is >> s, value = _Self(s), is;
}

inline friend std::ostream& operator <<(std::ostream& os, const _Self& value) {
return os << value.to_string();
}

inline int compareTo(const _Self& other) const {
if (_sign != other._sign) return _sign < other._sign ? -1 : +1;
if (!_sign) return 0;
int cmp = Compare(data(), size(), other.data(), other.size());
return _sign > 0 ? cmp : -cmp;
}

inline bool equals(const _Self& other) const {
if (_sign != other._sign) return false;
if (_bits == other._bits) return true;
return false;
}

static void DnM(const _Self& left, const _Self& right, _Self& q, _Self& r) {
if (!left._sign)
q = r = left;
else if (left.size() < right.size())
q = _Self(0), r = left;
else {
container cr = container(left._bits), cq = container(left.size() - right.size() + 1);
Divide(cr.data(), cr.size(), right.data(), right.size(), cq.data(), cq.size());
r = _Self(std::move(cr), left._sign < 0);
q = _Self(std::move(cq), (left._sign < 0) ^ (right._sign < 0));
}
}

public:
inline _Self operator +() const {
return _Self(_sign, _bits);
}

inline _Self operator -() const {
return _Self(-_sign, _bits);
}

inline bool operator !() const {
return _sign == 0;
}

inline friend bool operator <(const _Self& left, const _Self& right) {
return left.compareTo(right) < 0;
}

inline friend bool operator <=(const _Self& left, const _Self& right) {
return left.compareTo(right) <= 0;
}

inline friend bool operator >(const _Self& left, const _Self& right) {
return left.compareTo(right) > 0;
}

inline friend bool operator >=(const _Self& left, const _Self& right) {
return left.compareTo(right) >= 0;
}

inline friend bool operator ==(const _Self& left, const _Self& right) {
return left.equals(right);
}

inline friend bool operator !=(const _Self& left, const _Self& right) {
return !left.equals(right);
}

friend _Self operator +(_Self left, const _Self& right) {
return left += right;
}

friend _Self operator -(_Self left, const _Self& right) {
return left -= right;
}

friend _Self operator *(const _Self& left, const _Self& right) {
if (!left._sign) return left;
if (!right._sign) return right;
container bits = container(left.size() + right.size());
if (left.size() < right.size())
Multiply(right.data(), right.size(), left.data(), left.size(), bits.data(), bits.size());
else
Multiply(left.data(), left.size(), right.data(), right.size(), bits.data(), bits.size());
return _Self(std::move(bits), (left._sign < 0) ^ (right._sign < 0));
}

friend _Self operator /(const _Self& left, const _Self& right) {
if (!left._sign) return left;
if (left.size() < right.size())
return _Self(0);
else {
container local = container(left._bits), bits = container(left.size() - right.size() + 1);
Divide(local.data(), local.size(), right.data(), right.size(), bits.data(), bits.size());
return _Self(std::move(bits), (left._sign < 0) ^ (right._sign < 0));
}
}

friend _Self operator %(_Self left, const _Self& right) {
return left %= right;
}

friend _Self& operator +=(_Self& left, const _Self& right) {
if (!right._sign) return left;
if (!left._sign) return left = right;
if (left._sign != right._sign)
left = Subtract(left._bits, left._sign, right._bits, right._sign);
else
left = Add(left._bits, left._sign, right._bits, right._sign);
return left;
}

friend _Self& operator -=(_Self& left, const _Self& right) {
if (!right._sign) return left;
if (!left._sign) return left = -right;
if (left._sign != right._sign)
left = Add(left._bits, left._sign, right._bits, -right._sign);
else
left = Subtract(left._bits, left._sign, right._bits, right._sign);
return left;
}

friend _Self& operator *=(_Self& left, const _Self& right) {
return left = left * right;
}

friend _Self& operator /=(_Self& left, const _Self& right) {
return left = left / right;
}

friend _Self& operator %=(_Self& left, const _Self& right) {
if (!left._sign) return left;
if (left.size() < right.size()) return left;
Divide(left.data(), left.size(), right.data(), right.size(), container().data(), 0);
return left = _Self(std::move(left._bits), left._sign < 0);
}

friend _Self operator <<(const _Self& value, int shift) {
if (shift == 0)
return value;
else if (shift == INT_MIN)
return (value >> INT_MAX) >> 1;
else if (shift < 0) return value >> -shift;
int ds = shift / kcbitUint, ss = shift - (ds * kcbitUint);
container xd;
int xl;
bool negx = GetPartsForBitManipulation(value, xd, xl);
int zl = xl + ds + 1;
container zd = container(zl);
if (ss == 0)
for (int i = 0; i < xl; i++)
zd[i + ds] = xd[i];
else {
int carryShift = kcbitUint - ss, i;
uint carry = 0, rot;
for (i = 0; i < xl; i++)
rot = xd[i], zd[i + ds] = rot << ss | carry, carry = rot >> carryShift;
zd[i + ds] = carry;
}
return _Self(zd, negx);
}

friend _Self operator >>(const _Self& value, int shift) {
if (shift == 0)
return value;
else if (shift == INT_MIN)
return ((value << INT_MAX) << 1);
else if (shift < 0) return value << -shift;
int ds = shift / kcbitUint, ss = shift - (ds * kcbitUint);
container xd;
int xl;
bool negx = GetPartsForBitManipulation(value, xd, xl);
if (negx) {
if (shift >= (kcbitUint * xl)) return _Self(-1LL);
xd.resize(xl), DangerousMakeTwosComplement(xd);
}
int zl = xl - ds;
if (zl < 0) zl = 0;
container zd = container(zl);
if (ss == 0)
for (int i = xl - 1; i >= ds; i--)
zd[i - ds] = xd[i];
else {
int carryShift = kcbitUint - ss;
uint carry = 0, rot;
for (int i = xl - 1; i >= ds; i--) {
rot = xd[i];
zd[i - ds] = (rot >> ss) | ((negx && i == xl - 1) ? (0xFFFFFFFF << carryShift) : carry);
carry = (rot << carryShift);
}
}
if (negx) DangerousMakeTwosComplement(zd); // mutates zd
return _Self(zd, negx);
}

private:
static int Compare(const uint* l, int ll, const uint* r, int rl) {
if (ll ^ rl) return (ll < rl) ? -1 : 1;
for (int i = ll - 1; i >= 0; i--)
if (l[i] ^ r[i]) return (l[i] < r[i]) ? -1 : 1;
return 0;
}

static void StripLeadingZero(container& bits) {
const uint* data = bits.data();
uint len = bits.size();
while (len > 0 && data[len - 1] == 0)
--len;
bits.resize(len);
}

static _Self Add(container left, int ls, container right, int rs) {
container *l = &left, *s = &right;
if (l->size() < s->size()) std::swap(l, s);
uint ll = l->size(), sl = s->size();
long res = AddSelf(l->data(), ll, s->data(), sl);
if (res) l->push_back(res);
return _Self(std::move(*l), ls < 0);
}

static _Self Subtract(container left, int ls, container right, int rs) {
container *l = &left, *s = &right;
if (Compare(l->data(), l->size(), s->data(), s->size()) < 0) std::swap(l, s), ls = -ls;
uint ll = l->size(), sl = s->size();
SubtractSelf(l->data(), ll, s->data(), sl);
StripLeadingZero(*l);
return _Self(std::move(*l), ls < 0);
}

static long AddSelf(uint* l, int ll, const uint* r, int rl) {
long c = 0;
for (int i = 0; i < rl; i++)
c = (l[i] + c) + r[i], l[i] = c, c >>= 32;
for (int i = rl; c != 0 && i < ll; i++)
c = l[i] + c, l[i] = c, c >>= 32;
return c;
}

static long SubtractSelf(uint* l, int ll, const uint* r, int rl) {
long c = 0;
for (int i = 0; i < rl; i++)
c = (l[i] + c) - r[i], l[i] = c, c >>= 32;
for (int i = rl; c != 0 && i < ll; i++)
c = l[i] + c, l[i] = c, c >>= 32;
return c;
}

static void Multiply(const uint* l, int ll, const uint* r, int rl, uint* b, int bl) {
if (rl < MultiplyThreshold) {
for (int i = 0; i < rl; i++) {
ulong c = 0;
for (int j = 0; j < ll; j++)
c = b[i + j] + c + (ulong)l[j] * r[i], b[i + j] = c, c >>= 32;
b[i + ll] = c;
}
}
else {
int n = rl >> 1, n2 = n << 1;
const uint *llo = l, *lhi = l + n, *rlo = r, *rhi = r + n;
int llol = n, lhil = ll - n, rlol = n, rhil = rl - n;
uint *blo = b, *bhi = b + n2;
int blol = n2, bhil = bl - n2;
Multiply(llo, llol, rlo, rlol, blo, blol);
Multiply(lhi, lhil, rhi, rhil, bhi, bhil);
int lfl = lhil + 1, rfl = rhil + 1, col = lfl + rfl;
container lf(lhi, lhi + lhil);
lf.resize(lfl);
AddSelf(lf.data(), lfl, llo, llol);
container rf(rhi, rhi + rhil);
rf.resize(rfl);
AddSelf(rf.data(), rfl, rlo, rlol);
container co = container(col);
Multiply(lf.data(), lfl, rf.data(), rfl, co.data(), col);
SubtractSelf(co.data(), col, bhi, bhil);
SubtractSelf(co.data(), col, blo, blol);
AddSelf(b + n, bl - n, co.data(), col);
}
}

static void Divide(uint* l, int ll, const uint* r, int rl, uint* b, int bl) {
uint dHi = r[rl - 1], dLo = rl > 1 ? r[rl - 2] : 0;
int sh = __builtin_clz(dHi), bsh = 32 - sh;
if (sh > 0) {
uint dNx = rl > 2 ? r[rl - 3] : 0;
dHi = (dHi << sh) | (dLo >> bsh);
dLo = (dLo << sh) | (dNx >> bsh);
}
for (int i = ll; i >= rl; i--) {
int n = i - rl;
uint t = i < ll ? l[i] : 0;
ulong vHi = ((ulong)t << 32) | l[i - 1];
uint vLo = i > 1 ? l[i - 2] : 0;
if (sh > 0) {
uint vNx = i > 2 ? l[i - 3] : 0;
vHi = (vHi << sh) | (vLo >> bsh);
vLo = (vLo << sh) | (vNx >> bsh);
}
ulong d = std::min(vHi / dHi, 0xFFFFFFFFULL);
while (DivideGuessTooBig(d, vHi, vLo, dHi, dLo))
--d;
if (d > 0 && SubtractDivisor(l + n, ll - n, r, rl, d) != t)
AddDivisor(l + n, ll - n, r, rl), --d;
if (bl != 0) b[n] = (uint)d;
if (i < ll) l[i] = 0;
}
}

static uint AddDivisor(uint* l, int ll, const uint* r, int rl) {
ulong c = 0;
for (int i = 0; i < rl; i++)
c = (l[i] + c) + r[i], l[i] = c, c >>= 32;
return c;
}

static uint SubtractDivisor(uint* l, int ll, const uint* r, int rl, ulong q) {
ulong c = 0;
for (int i = 0; i < rl; i++) {
c += r[i] * q;
uint digit = (uint)c;
c = (c >> 32) + (l[i] < digit), l[i] -= digit;
}
return c;
}

static bool DivideGuessTooBig(ulong q, ulong vHi, uint vLo, uint dHi, uint dLo) {
ulong cHi = dHi * q, cLo = dLo * q;
cHi = cHi + (cLo >> 32), cLo = cLo & 0xFFFFFFFF;
if (cHi ^ vHi) return cHi > vHi;
if (cLo ^ vLo) return cLo > vLo;
return false;
}

inline static bool GetPartsForBitManipulation(const _Self& x, container& xd, int& xl) {
if (x._bits.empty())
xd.assign(1, (x._sign < 0) ? (uint)-x._sign : (uint)x._sign);
else
xd = x._bits;
xl = (x._bits.empty() ? 1 : x._bits.size());
return x._sign < 0;
}

static void DangerousMakeTwosComplement(container& d) {
if (!d.empty() && d.size() > 0) {
d[0] = ~d[0] + 1;
uint i = 1;
for (; d[i - 1] == 0 && i < d.size(); i++)
d[i] = ~d[i] + 1;
for (; i < d.size(); i++)
d[i] = ~d[i];
}
}

static std::string FormatBigInt(const _Self& value) {
if (value._sign == 0) return "0";
const uint kuBase = 1000000000;
const int kcchBase = 9;
int d = 0, cs = value._bits.size(), cd = 0;
container rd = container(cs * 10 / 9 + 2);
for (int is = cs; --is >= 0;) {
uint uc = value._bits[is];
for (int id = 0; id < cd; id++) {
ulong ur = ((ulong)rd[id] << kcbitUint) | uc;
rd[id] = (uint)(ur % kuBase), uc = (uint)(ur / kuBase);
}
if (uc != 0) {
rd[cd++] = uc % kuBase, uc /= kuBase;
if (uc != 0) rd[cd++] = uc;
}
}
int cm = cd * kcchBase;
if (d > 0 && d > cm) cm = d;
if (value._sign < 0) cm = cm + 1;
char* s = new char[cm + 1];
int id = cm;
for (int iuDst = 0; iuDst < cd - 1; iuDst++) {
uint ud = rd[iuDst];
for (int cch = kcchBase; --cch >= 0;)
s[--id] = (char)('0' + ud % 10), ud /= 10;
}
for (uint uDig = rd[cd - 1]; uDig != 0;)
s[--id] = (char)('0' + uDig % 10), uDig /= 10;
for (int t = cm - id; d > 0 && d > t;)
s[--id] = '0', d--;
if (value._sign < 0) s[--id] = '-';
return std::string(s + id, s + cm);
}
};
// class BigInt
#undef long
} // namespace csl

namespace std {
inline csl::BigInt abs(const csl::BigInt& x) {
return x.abs();
}
inline string to_string(const csl::BigInt& x) {
return x.to_string();
}
} // namespace std

#endif /* BIGINT_H_ */
bigint_exam.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
* Name : bigint_exam.cpp
* Author : CHN.ChouUn
* Date : 2015年5月5日 下午7:00:52
* Copyright : www.fateud.com
* Description : None
*/


//@ Including Header
#include <csl_std.h>
#include <bigint.h>
//@ Program Begin

//@ Main Function
int main() {
int _;
std::cin >> _;
while (_--) {
csl::BigInt<300> n;
std::cin >> n;
if (n % 2 == 1)
std::cout << (n / 2) << std::endl;
else if (n % 4 > 0)
std::cout << (n / 2 - 2) << std::endl;
else
std::cout << (n / 2 - 1) << std::endl;
if (_) std::cout << std::endl;
}
return 0;
}

离散化

discrete.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Name : Discretization 离散化
// Copyright : fateud.com
#ifndef DISCRETE_H_
#define DISCRETE_H_ 20150926L
#include <vector>
#include <algorithm>
namespace csl {
template<typename _Tp>
struct discrete {
typedef std::size_t size_type;

void build() {
std::sort(data.begin(), data.end());
data.resize(std::unique(data.begin(), data.end()) - data.begin());
}
inline void clear() {
data.clear();
}
inline size_type size() const {
return data.size();
}
inline void reserve(size_type __n) {
data.reserve(__n);
}

inline size_type query(const _Tp& __x) const {
return std::lower_bound(data.begin(), data.end(), __x) - data.begin();
}
_Tp operator [](size_type __x) const {
return data[__x];
}
inline void insert(_Tp __x) {
data.push_back(__x);
}
template<typename _InputIterator>
inline void insert(_InputIterator first,_InputIterator last) {
data.insert(data.end(), first, last);
}

std::vector<_Tp> data;
};
} // namespace csl

#endif /* DISCRETE_H_ */

欧拉筛法

快速数论变换

图论

前向星

graph.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
// Name : Graph 图论
// Copyright : fateud.com

#ifndef GRAPH_H_
#define GRAPH_H_ 20150911L

#include <vector>

namespace csl {
template<typename _Tp>
struct _graph_node {
typedef _Tp value_type;
typedef std::size_t size_type;

typedef _graph_node<_Tp>* _Link;
typedef _graph_node<_Tp> _Self;

_graph_node() :
prev(), next(), from(), to(), data() {
}

_graph_node(_Link a,_Link b,size_type c,size_type d,value_type e) :
prev(a), next(b), from(c), to(d), data(e) {
}

_Link prev;
_Link next;
size_type from;
size_type to;
value_type data;
};

template<typename _Tp>
struct graph {
// template parameter.
typedef _Tp value_type;
typedef _Tp* pointer;
typedef _Tp& reference;

typedef _graph_node<_Tp>* iterator;

typedef _graph_node<_Tp> _Node;
typedef _graph_node<_Tp>* _Link;
typedef graph<_Tp> _Self;

typedef std::size_t size_type;

// member function.
void m_add_edge(size_type from,size_type to,const value_type& data) {
_Link node = m_data.data() + m_size++;
*node = _Node(0, m_impl[from], from, to, data);
if(m_impl[from]) m_impl[from]->prev = node;
m_impl[from] = node;
}

// constructor & destructor.
explicit graph(size_type __v = 0,size_type __e = 0) :
m_size() {

m_impl.reserve(__v);
m_data.reserve(__e);
}

// iterators.

// capacity.
inline void build(size_type __v,size_type __e) {
m_impl.assign(__v, _Link());
m_data.resize(__e);
m_size = 0;
}

inline size_type size() const {
return m_size;
}

// element access.
inline _Link getHead(size_type __x) const {
return m_impl[__x];
}

inline _Link getEdge(size_type __x) {
return m_data.data() + __x;
}

inline size_type getEdgeIndex(_Link __x) const {
return __x - m_data.data();
}

// modifiers.
inline void add_edge(size_type from,size_type to,const value_type& data) {
m_add_edge(from, to, data);
}

inline void add_double_edge(size_type from,size_type to,
const value_type& data)
{

m_add_edge(from, to, data);
m_add_edge(to, from, data);
}

inline void add_couple_edge(size_type from,size_type to,
const value_type& data1,const value_type& data2 = value_type())
{

m_add_edge(from, to, data1);
m_add_edge(to, from, data2);
}

// operator overloading.

// specialized algorithms.

// member variable.
std::vector<_Link> m_impl;
std::vector<_Node> m_data;
size_type m_size;

};

template<typename _Tp>
struct tarjan {
public:
typedef typename graph<_Tp>::_Link _Link;

typedef std::size_t size_type;

private:
void __scc(size_type u) {
dfn[u] = low[u] = ++idx;
vis[u] = true;
sta.push_back(u);
for(_Link i = map->getHead(u); i; i = i->next) {
size_type v = i->to;
if(!dfn[v]) {
__scc(v);
if(low[u] > low[v]) low[u] = low[v];
}
else {
if(vis[v] && low[u] > dfn[v]) low[u] = dfn[v];
}
}
if(dfn[u] == low[u]) {
size_type w;
do {
w = sta.back();
sta.pop_back();
vis[w] = false;
key[w] = cnt;
}while(w != u);
++cnt;
}
}

void __dcc(size_type u,size_type p) {
dfn[u] = low[u] = ++idx;
sta.push_back(u);
for(_Link i = map->getHead(u); i; i = i->next) {
size_type v = i->to;
if(v == p) continue;
if(!dfn[v]) {
__dcc(v, u);
if(low[u] > low[v]) low[u] = low[v];
if(dfn[u] < low[v]) {
size_type w;
do {
w = sta.back();
sta.pop_back();
key[w] = cnt;
}while(w != v);
cnt++;
}
}
else {
if(low[u] > dfn[v]) low[u] = dfn[v];
}
}
}

public:
void scc(graph<_Tp>& __map) {
map = &__map;
size_type __n = map->m_impl.size();
idx = 0;
cnt = 0;
sta.reserve(__n);
dfn.assign(__n, 0);
low.resize(__n);
key.resize(__n);
vis.assign(__n, false);

for(size_type i = 0; i < __n; ++i)
if(!dfn[i]) __scc(i);
}

void dcc(graph<_Tp>& __map) {
map = &__map;
size_type __n = map->m_impl.size();
idx = 0;
cnt = 0;
sta.reserve(__n);
dfn.assign(__n, 0);
low.resize(__n);
key.resize(__n);

for(size_type i = 0; i < __n; ++i) {
if(dfn[i]) continue;
sta.clear();
__dcc(i, -1);
for(size_type j = 0; j < sta.size(); ++j)
key[sta[j]] = cnt;
cnt++;
}
}

inline size_type operator[](const size_type __x) const {
return key[__x];
}

inline size_type size() const {
return cnt;
}

private:
graph<_Tp>* map;
size_type idx;
size_type cnt;
std::vector<size_type> sta;
std::vector<size_type> dfn;
std::vector<size_type> low;
std::vector<size_type> key;
std::vector<bool> vis;
};

} // namespace csl

#endif /* GRAPH_H_ */

强联通分量

2-SAT

网络流

字符串

马拉车算法

manacher.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// Name : Manacher Algorithm 马拉车算法
// Copyright : fateud.com

#ifndef MANACHER_H_
#define MANACHER_H_ 20150814L

#include <vector>

namespace csl {
template<typename _Tp = char,_Tp _FlagS = '@',_Tp _FlagD = '#',_Tp _FlagT =
'\0'>
struct manacher {
// template parameter.
typedef _Tp key_type;
typedef int value_type;
typedef std::size_t size_type;

void generate(const key_type* __src) {
m_dest.clear();
m_dest.push_back(_FlagS), m_dest.push_back(_FlagD);
for(size_type i = 0; __src[i] != _FlagT; i++)
m_dest.push_back(__src[i]), m_dest.push_back(_FlagD);
m_dest.push_back(_FlagT);
m_size = m_dest.size();
}

void calculate() {
m_data.resize(m_size);
for(int i = 1, j = 0, p = 0; i < m_size; ++i) {
register int k = (p > i) ? std::min(m_data[2 * j - i], p - i) : 1;
while(m_dest[i + k] == m_dest[i - k])
++k;
if(k + i > p) p = k + i, j = i;
m_data[i] = k;
}
}

// capacity.
inline void build(const key_type* __src) {
generate(__src);
calculate();
}

size_type size() const {
return m_size - 4;
}

// element access.
value_type query() const {
value_type __res = value_type();
for(size_type i = 0; i < m_size; ++i)
if(m_data[i] > __res) __res = m_data[i];
return __res - 1;
}

value_type at(size_type __x) {
return __x + 2 < m_size ? this->operator[](__x) : 0;
}

value_type operator [](size_type __x) const {
return m_data[__x + 2] - 1;
}

// member variable.
std::vector<key_type> m_dest;
std::vector<value_type> m_data;
size_type m_size;

};

} // namespace csl

#endif /* MANACHER_H_ */

AC自动机

后缀自动机

其他

珍爱生命,远离爆栈

文章目录
  1. 1. 使用方法
  2. 2. 更新日志
  3. 3. 通用文件头
    1. 3.1. 纸农の标准库
    2. 3.2. 数学计算
    3. 3.3. 算法
  4. 4. 存储结构
    1. 4.1. 前向链表
  5. 5. 统计结构
    1. 5.1. 树状数组
    2. 5.2. 线段树
    3. 5.3. 稀疏表
  6. 6. 数论
    1. 6.1. 矩阵
    2. 6.2. 高精度正整数
    3. 6.3. 离散化
    4. 6.4. 欧拉筛法
    5. 6.5. 快速数论变换
  7. 7. 图论
    1. 7.1. 前向星
    2. 7.2. 强联通分量
    3. 7.3. 2-SAT
    4. 7.4. 网络流
  8. 8. 字符串
    1. 8.1. 马拉车算法
    2. 8.2. AC自动机
    3. 8.3. 后缀自动机
  9. 9. 其他
    1. 9.1. 珍爱生命,远离爆栈