wth2026's blog

记录我的学校生活

代码模板

发表于 更新于

1.工具

1.read（快读）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<20, stdin), p1 == p2) ? EOF : *p1 ++)
char *p1 ,*p2, buf[1 << 20 + 5];

inline int read() {
	int x = 0, f = 1;
	char c = gc();
	
	while (!isdigit(c)) {
		if (c == '-') {
			f *= -1;
		}
		
		c = gc();
	}
	
	while (isdigit(c)) {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = gc();
	}
	
	return x * f;
}

2.write（快输）

1
2
3
4
5
6
7
8
9
10
11
12
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	
	if (x > 9) {
		print(x / 10);
	}
	
	putchar('0' + x % 10);
}

2.数据结构

1.Heap(堆)

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
struct Heap {
	int h[1000005], size;
	
	void clean() {
		memset(h, 0, sizeof(0));
		size = 0;
	}
	
	void down(int u) {
		int t = u;
		
		if (u * 2 <= size && h[u * 2] < h[t]) {
			t = u * 2;
		}
		
		if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) {
			t = u * 2 + 1;
		}
		
		if (u != t) {
			swap(h[u], h[t]);
			down(t);
		}
	}
	
	void up(int u) {
		while (u / 2 > 0 && h[u / 2] > h[u]) {
			swap(h[u / 2], h[u]);
			u /= 2;
		}
	}
	
	int top() {
		return h[1];
	}
	
	void push(int k) {
		h[++ size] = k;
		up(size);
	}
	
	void pop() {
		h[1] = h[size];
		-- size;
		down(1);
	}
};

2.BIT(树状数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct BIT {
	int c[500005], n;
	
	int loubit(int s) {
		return s & -s;
	}
	
	void add(int k, int x) {
		for (int i = k; i <= n; i += loubit(i)) {
			c[i] += x;
		}
	}
	
	int ask(int k) {
		int ans = 0;
		
		for (int i = k; i; i -= loubit(i)) {
			ans += c[i];
		}
		
		return ans;
	}
};

3.FHQ Treap（无旋平衡树）

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
template <size_t N>
	class FHQ_Treap {
		private :
			int cnt = 0, root = 0, dl = 0, dr = 0, temp = 0;
			
			struct treap {
				int l, r, key, pro, num, size;
			} tr[N + 5];
			
			void pushup (int k) {
				tr[k].size = tr[tr[k].l].size + tr[tr[k].r].size + 1;
			}
			
			int newtreap (int x) {
				tr[++ cnt].key = x;
				tr[cnt].pro = rand ();
				tr[cnt].num = tr[cnt].size = 1;
				return cnt;
			}
			
			void split (int pos, int xx, int& l, int& r) {
				if (!pos) {
					l = r = 0;
					return;
				}
				
				if (tr[pos].key <= xx) {
					l = pos;
					split (tr[l].r, xx, tr[l].r, r);
				} else {
					r = pos;
					split (tr[r].l, xx, l, tr[r].l);
				}
				
				pushup (pos);
			}
			
			int merge (int l, int r) {
				if (!l || !r) {
					return l | r;
				}
				
				if (tr[l].pro <= tr[r].pro) {
					tr[l].r = merge (tr[l].r, r);
					pushup (l);
					return l;
				} else {
					tr[r].l = merge (l, tr[r].l);
					pushup (r);
					return r; 
				}
			}
			
		protected :
		
		public :
			void Insert (int xx) {
				split (root, xx - 1, dl, dr);
				root = merge (merge (dl, newtreap (xx)), dr);
			}
			
			void Delete (int xx) {
				split (root, xx - 1, dl, dr);
				split (dr, xx, temp, dr);
				temp = merge (tr[temp].l, tr[temp].r);
				root = merge (dl, merge (temp, dr));
			}
			
			int Get_Rank (int xx) {
				split (root, xx - 1, dl, dr);
				int rank = tr[dl].size + 1;
				root = merge (dl, dr);
				return rank;
			}
			
			int Get_Num (int pos, int k = root) {
				int lsize = tr[tr[pos].l].size + 1;
				
				if (lsize == k) {
					return tr[pos].key;
				}
				
				if (lsize > k) {
					return Get_Num (tr[pos].l, k);
				} else {
					return Get_Num (tr[pos].r, k - lsize);
				}
			}
			
			int Get_Last (int xx) {
				split (root, xx - 1, dl, dr);
				int last = Get_Num (dl, tr[dl].size);
				root = merge (dl, dr);
				return last;
			}
			
			int Get_Next (int xx) {
				split (root, xx, dl, dr);
				int next = Get_Num (dr, 1);
				root = merge (dl, dr);
				return next;
			}
			
			void Delete_All (int k) {
				int _1, _2, _3, _4;
				split (root, k - 1, _1, _2);
				split (_2, k, _3, _4);
				merge (_1, _4);
			}
		
	} ;

4.Splay(旋转BST)

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
struct Splay {
	int root, cnt;
	
	struct Node {//节点 
		int tree_size, size, val, fa, son[2];
	} tr[N + 5];
	
	void Push_Up(int k) {//上传标记 
		tr[k].tree_size = tr[tr[k].son[0]].tree_size + tr[tr[k].son[1]].tree_size + tr[k].size;
	}
	
	int Get(int x) {//求是那个儿子 
		if (x == tr[tr[x].fa].son[0]) {
			return 0;
		} else {
			return 1;
		}
	}
	
	void rotate(int x) {//旋转 
		int y = tr[x].fa, z = tr[y].fa, d = Get(x);
		tr[y].son[d] = tr[x].son[d ^ 1];

		if (tr[x].son[d ^ 1]) {
			tr[tr[x].son[d ^ 1]].fa = y;
		}

		tr[x].son[d ^ 1] = y;
		tr[y].fa = x;

		if (z) {
			tr[z].son[y == tr[z].son[1]] = x;
		}

		tr[x].fa = z;
		Push_Up(y);
		Push_Up(x);
	}
	
	void splay(int x) {//伸展 
		while (tr[x].fa) {
			int y = tr[x].fa, z = tr[y].fa;

			if (z) {
				if (Get(x) ^ Get(y)) {
					rotate(x);
				} else {
					rotate(y);
				}
			}

			rotate(x);
		}

		root = x;
	}
	
	int Get_Rank(int x) {//求一个数的排名 
		int k = root, res = 1;

		while (k) {
			if (x == tr[k].val) {
				res += tr[tr[k].son[0]].tree_size;
				splay(k);
				return res;
			}

			if (x < tr[k].val) {
				k = tr[k].son[0];
			} else {
				res += tr[tr[k].son[0]].tree_size + tr[k].size;
				k = tr[k].son[1];
			}
		}

		return res;
	}
	
	int Get_Num(int x) {//求一个排名的数 
		int k = root;

		while (k) {
			int _ = tr[tr[k].son[0]].tree_size;

			if (x <= _) {
				k = tr[k].son[0];
			} else if (_ + tr[k].size >= x) {
				break;
			} else {
				x -= _ + tr[k].size;
				k = tr[k].son[1];
			}
		}

		splay(k);
		return tr[k].val;
	}
	
	void Insert(int x) {//插入一个数 
		if (!root) {
			root = ++ cnt;
			tr[root].tree_size = tr[root].size = 1;
			tr[root].val = x;
			return;
		}

		int _ = 0, k = root;

		while (k) {
			if (x == tr[k].val) {
				break;
			}

			_ = k;
			k = tr[k].son[x > tr[k].val];
		}

		if (!k) {
			k = ++ cnt;
			tr[_].son[x > tr[_].val] = k;
			tr[k].fa = _;
			tr[k].val = x;
		}

		++ tr[k].size;
		Push_Up(k);
		Push_Up(_);
		splay(k);
	}
	
	
///	void Insert(int k) {//插入 
//		if (!root) {
//			tr[++ cnt].val = k;
//			++ tr[cnt].size;
//			root = cnt;
//			Push_Up(cnt);
//			return;
//		}
//		
//		int _ = root, f = 0;
//		
//		while (1) {
//			if (tr[_].val == k) {
//				++ tr[_].size;
//				Push_Up(_);
//				Push_Up(f);
//				splay(_);
//				break;
//			}
//			
//			f = _;
//			_ = tr[_].son[tr[_].val < k];
//			
//			if (!_) {
//				tr[++ cnt].val = k;
//				++ tr[cnt].size;
//				tr[cnt].fa = f;
//				tr[f].son[tr[_].val < k] = cnt;
//				Push_Up(cnt);
//				Push_Up(f);
//				splay(cnt);
//				break;
//			}
//		}
//	}
//	
	void Delete(int x) {//删除一个数 
		int _ = 0, k = root;

		while (k) {
			if (x == tr[k].val) {
				break;
			}

			_ = k;
			k = tr[k].son[x > tr[k].val];
		}

		splay(k);

		if (tr[k].size == 1) {
			int p = tr[k].son[0];

			if (!p) {
				root = tr[k].son[1];
				tr[root].fa = 0;
				return;
			}

			while (tr[p].son[1]) {
				p = tr[p].son[1];
			}

			splay(p);
			tr[p].son[1] = tr[k].son[1];
			tr[tr[k].son[1]].fa = p;
			Push_Up(p);
		} else {
			-- tr[k].size;
			Push_Up(k);
		}
	}
	
	void Delete_All(int x) {//删除一个数的所有 
		int _ = 0, k = root;
	
		while (k) {
			if (x == tr[k].val) {
				break;
			}
	
			_ = k;
			k = tr[k].son[x > tr[k].val];
		}
	
		splay(k);
		int p = tr[k].son[0];
		
		if (!p) {
			root = tr[k].son[1];
			tr[root].fa = 0;
			return;
		}
	
		while (tr[p].son[1]) {
			p = tr[p].son[1];
		}
			
		splay(p);
		tr[p].son[1] = tr[k].son[1];
		tr[tr[k].son[1]].fa = p;
		Push_Up(p);
	}
	
	int Get_Last(int x) {//求一个数的前驱 
		Insert(x);
		int k = tr[root].son[0];

		while (tr[k].son[1]) {
			k = tr[k].son[1];
		}

		splay(k);
		Delete(x);
		return tr[k].val;
	}
	
	int Get_Next(int x) {//求一个数的后继 
		Insert(x);
		int k = tr[root].son[1];

		while (tr[k].son[0]) {
			k = tr[k].son[0];
		}

		splay(k);
		Delete(x);
		return tr[k].val;
	}
}

5.Persistent Segment Tree(可持久化线段树)

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
struct Persistent_Segment_Tree {
	int Root[N + 5], cnt, Root_Num;
	
	struct Node {
		int l, r, lson, rson, val;
	} tr[(N << 5) + 5];
	
	//---------------------------------
	
	int New_Node() {
		return ++ cnt;
	}
	
	void Init() {
		cnt = 0;
		Root_Num = 0;
		Root[0] = New_Node();
	}
	
	void build(int k, int l, int r, int a[]) {
		tr[k].l = l;
		tr[k].r = r;
		
		if (l == r) {
			tr[k].val = a[l];
			return;
		}
		
		tr[k].lson = New_Node();
		tr[k].rson = New_Node();
		int mid = (l + r) >> 1;
		build(tr[k].lson, l, mid, a);
		build(tr[k].rson, mid + 1, r, a);
	}
	
	void edit(int k, int x, int v) {
		if (tr[k].l == tr[k].r) {
			tr[k].val = v;
			return;
		}
		
		int mid = tr[tr[k].lson].r;
		Node _;
		
		if (x <= mid) {
			_ = tr[tr[k].lson];
			tr[k].lson = New_Node();
			tr[tr[k].lson] = _;
			edit(tr[k].lson, x, v);
		} else {
			_ = tr[tr[k].rson];
			tr[k].rson = New_Node();
			tr[tr[k].rson] = _;
			edit(tr[k].rson, x, v);
		}
	}
	
	int query(int k, int x) {
		if (tr[k].l == tr[k].r) {
			return tr[k].val;
		}
		
		int mid = tr[tr[k].lson].r;
		
		if (x <= mid) {
			return query(tr[k].lson, x);
		} else {
			return query(tr[k].rson, x);
		}
	}
	
	void Build(int n, int a[]) {
		build(Root[0], 1, n, a);
	}
	
	void Edit(int x, int v, int opt) {
		Root[++ Root_Num] = New_Node();
		tr[Root[Root_Num]] = tr[Root[opt]];
		edit(Root[Root_Num], x, v);
	}
	
	int Query(int opt, int x) {
		Root[++ Root_Num] = New_Node();
		tr[Root[Root_Num]] = tr[Root[opt]];
		return query(Root[Root_Num], x);
	}
}

3.组合数学

1.C

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
int ksm(int a, int b, int mod) {
    int ans = 1;

    while (b) {
        if (b & 1) {
            ans *= a;
            ans %= mod;
        }

        a *= a;
        a %= mod;
        b >>= 1;
    }

    return ans;
}

int jc[300005];

void init(int mod) {
    jc[0] = 1;

    for (int i = 1; i < 300005; ++ i) {
        jc[i] = jc[i - 1] * i % mod;
    }
}

int C(int _, int __, int mod) {
	if (_ < __) {
		return 0;
	}
	
    return jc[_] * ksm(jc[__], mod - 2, mod) % mod * ksm(jc[_ - __], mod - 2, mod) % mod;
}

4.图论

1.Tarjan（无向图）

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
#define Min(x,y) (x=min(x,y))
int dfn[N], low[N], cnt, SCC[N], _Sz[N];
bool _Flg[N];
stack <int> _Stck;
vector <int> _Mp[N];

void tarjan (int id, int fa) {
	if (dfn[id]) {
		if (_Flg[id]) {
			Min (low[fa], dfn[id]);
		}
		
		return ;
	}
	
	dfn[id] = ++ cnt;
	low[id] = dfn[id];
	_Stck.push (id);
	_Flg[id] = 1;
	
	for (auto it : _Mp[id]) {
		if (it ^ fa) {
			tarjan (it, id);
			Min (low[id], low[it]);
		}
	}
	
	if (dfn[id] == low[id]) {
		++ SCC[0];
		
		while (_Stck.top () ^ id) {
			SCC[_Stck.top ()] = SCC[0];
			++ _Sz[SCC[0]];
			_Flg[_Stck.top ()] = 0;
			_Stck.pop ();
		}
		
		SCC[_Stck.top ()] = SCC[0];
		++ _Sz[SCC[0]];
		_Flg[_Stck.top ()] = 0;
		_Stck.pop ();
	}
}

2.费用流

1) EK

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
class Edge {
  private :
  
  protected :
  
  public :
    int to, v, w, c;
    
    void operator () (int T, int V, int W, int C) {
      to = T;
      v = V;
      w = W;
      c = C;
    }
    
    int& operator ~ () {
      return to;
    }
    
    int& operator ! () {
      return v;
    }
    
    int& operator & () {
      return w;
    }
    
    int& operator * () {
      return c;
    }
  
} ;

const int N = 5e3 + 5, M = 1e5 + 5;

int n, m, s, t;
int u, v, w, c;
int cnt, h[N];
Edge _Mp[M];
int _Ds[N], _Pth[N], _Flw_Cst[N];
bool _Flg[N];
int _Mx_Flw, _Mn_Cst;
queue <int, list <int>> _Q;
int _;

void Add_Edge (int U, int V, int W, int C) {
  _Mp[++ cnt] (h[U], V, W, C);
  h[U] = cnt;
}

void Add_Flow (int U, int V, int W, int C) {
  Add_Edge (U, V, W, C);
  Add_Edge (V, U, 0, -C);
}

bool SPFA () {
  memset (_Ds, inf, sizeof (_Ds));
  memset (_Flg, 0, sizeof (_Flg));
  
  while (_Q.size ()) {
    _Q.pop ();
  }
  
  _Q.push (s);
  _Ds[s] = 0;
  _Flw_Cst[s] = lnf;
  _Flw_Cst[t] = 0;
  
  while (_Q.size ()) {
    _ = _Q.front ();
//			cout << "\t" << _ << endl;
    _Q.pop ();
    _Flg[_] = 0;
    
    for (register int i = h[_]; i; i = (~ _Mp[i])) {
      if (! (& _Mp[i]) || _Ds[! _Mp[i]] <= _Ds[_] + (* _Mp[i])) {
        continue ;
      }
      
      _Ds[! _Mp[i]] = _Ds[_] + (* _Mp[i]);
      _Flw_Cst[! _Mp[i]] = min ((& _Mp[i]), _Flw_Cst[_]);
      _Pth[! _Mp[i]] = i;
      
      if (! _Flg[! _Mp[i]]) {
        _Q.push (! _Mp[i]);
        _Flg[! _Mp[i]] = 1;
      }
    }
  }
  
  return _Flw_Cst[t];
}

void Edit () {
  _Mx_Flw += _Flw_Cst[t];
  
  for (register int i = t; i ^ s; i = (! _Mp[_Pth[i] ^ 1])) {
    (& _Mp[_Pth[i]]) -= _Flw_Cst[t];
    (& _Mp[_Pth[i] ^ 1]) += _Flw_Cst[t];
    _Mn_Cst += _Flw_Cst[t] * (* _Mp[_Pth[i]]);
  }
}

5.数学

1.傅里叶变换

1)分治DFT

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
const int N = (1 << 21) + 5;
const double pi = acos (-1.0);
const complex <double> I (0, 1);

complex <double> a[N], b[N], _Tmp[N], _, __;

void DFT (complex <double> * _Cmplx, int n, int re) {
	if (n == 1) {
		return ;
	}
	
	for (register int i = 0; i ^ n; ++ i) {
		_Tmp[i] = _Cmplx[i];
	}
	
	for (register int i = 0; i ^ n; ++ i) {
		if (i & 1) {
			_Cmplx[(i >> 1) + (n >> 1)] = _Tmp[i];
		} else{
			_Cmplx[(i >> 1)] = _Tmp[i];
		}
	}
	
	DFT (_Cmplx, n >> 1, re);
	DFT ((_Cmplx + (n >> 1)), n >> 1, re);
	
	_  = complex <double> (cos (2 * pi / n), sin (2 * pi * re / n));
	__ = complex <double> (1, 0);
	
	for (register int i = 0; i ^ (n >> 1); ++ i) {
		_Tmp[i] = _Cmplx[i] + __ * _Cmplx[i + (n >> 1)];
		_Tmp[i + (n >> 1)] = _Cmplx[i] - __ * _Cmplx[i + (n >> 1)];
		__ *= _;
	}
	
	for (register int i = 0; i ^ n; ++ i) {
		_Cmplx[i] = _Tmp[i];
	}
}

int n, m;
//	int IO;
int nm;

void Main () {
	nm = 1;
	cin >> n >> m;
	
	while (nm <= n + m) {
		nm <<= 1;
	}
	
	for (register int i = 0; i <= n; ++ i) {
		cin >> a[i];
	}
	
	for (register int i = 0; i <= m; ++ i) {
		cin >> b[i];
	}
	
//		for (register int i = 0; i <= n; ++ i) {
//			cout << '\t' << i << ' ' << a[i] << endl;
//		}
//		
//		cout << nm << endl;
	DFT (a, nm, 1);
	DFT (b, nm, 1);
	
	for (register int i = 0; i <= nm; ++ i) {
		a[i] *= b[i];
	}
	
	DFT (a, nm, -1);
	
	for (register int i = 0; i <= n + m; ++ i) {
		cout << (int) (floor ((a[i].real () / nm) + 0.5)) << ' ';
	}
	
	cout << endl;
}

2）倍增FFT

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
const int N = (1 << 21) + 5;
const double pi = acos (-1.0);

int n, m;
int nm;
complex <double> a[N], b[N], _, __;
int l, r[N];

void FFT (complex <double> * _Cmplx, int re) {
	for (register int i = 0; i ^ nm; ++ i) {
		if (i < r[i]) {
			swap (_Cmplx[i], _Cmplx[r[i]]);
		}
	}
	
	for (register int i = 1; i ^ nm; i <<= 1) {
		_ = complex <double> (cos (pi / i), sin (pi / i) * re);
		
		for (register int j = 0; j ^ nm; j += (i << 1)) {
			__  = complex <double> (1, 0);
			
			for (register int k = 0; k ^ i; ++ k) {
				complex<double> x = _Cmplx[j + k], y = __ * _Cmplx[i + j + k];
				_Cmplx[j + k] = x + y;
				_Cmplx[i + j + k] = x - y;
				__ *= _;
			}
		}
	}
}

void Main () {
	nm = 1;
	l = 0;
	cin >> n >> m;
	
	while (nm <= n + m) {
		nm <<= 1;
		++ l;
	}
	
	for (register int i = 0; i ^ nm; ++ i) {
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
	}
	
	for (register int i = 0; i <= n; ++ i) {
		cin >> a[i];
	}
	
	for (register int i = 0; i <= m; ++ i) {
		cin >> b[i];
	}
	
	FFT (a, 1);
	FFT (b, 1);
	
	for (register int i = 0; i <= nm; ++ i) {
		a[i] *= b[i];
	}
	
	FFT (a, -1);
	
	for (register int i = 0; i <= n + m; ++ i) {
		cout << (int) (floor ((a[i].real () / nm) + 0.5)) << ' ';
	}
	
	cout << endl;
}

6.其他算法

1.Bsearch(二分)

1）寻找满足check() == true的第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Bsearch(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        
        if (check(mid)) {
        	r = mid;
        }
        else {
        	l = mid + 1;
        }
    }
    
    return l;
}

2）寻找满足check() == true的最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Bsearch(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        
        if (check(mid)) {
        	l = mid;
        }
        else {
        	r = mid - 1;
        }
    }
    
    return l;
}