catch22-algorithm-template.tex

% !TeX program = xelatex 

%文档类型
\documentclass[a4paper]{ctexart}

%引用包裹
\usepackage{bm}
\usepackage{cmap}
\usepackage{cite}
\usepackage{color}
\usepackage{float}
\usepackage{xeCJK}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{setspace}
\usepackage{geometry}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage{indentfirst}
\usepackage[cache=false]{minted}
\usepackage{fontspec}
\usepackage{pdfpages}
\usepackage{fancyhdr}
\usepackage[table]{xcolor}
\usepackage{booktabs}
\usepackage{harpoon}
%代码高亮
\geometry{margin=1in}
\setmonofont{Consolas}
%字体设置
\setmainfont{Consolas}
%\setCJKmonofont{SimSun}
%\setCJKmainfont[BoldFont={SimSun}]{SimSun}

\hypersetup{
	colorlinks=true,
	linkcolor=black
}

\newcommand{\cppcode}[1]{
	\inputminted[mathescape,
	tabsize=2,
	linenos,
	%frame=single,
	framesep=2mm,
	breakaftergroup=true,
	breakautoindent=true,
	breakbytoken=true,
	breaklines=true,
	fontsize=\small
	]{cpp}{#1}
}

%\newcommand{\javacode}[1]{
%	\inputminted[mathescape,
%	tabsize=2,
%	linenos,
%	%frame=single,
%	framesep=2mm,
%	breakaftergroup=true,
%	breakbytoken=true,
%	breaklines=true,
%	fontsize=\small
%	]{java}{#1}
%}

%\newcommand{\vimcode}[1]{
%	\inputminted[mathescape,
%	tabsize=2,
%	linenos,
%	%frame=single,
%	framesep=2mm,
%	breakaftergroup=true,
%	breakautoindent=true,
%	breakbytoken=true,
%	breaklines=true,
%	fontsize=\small
%	]{vim}{#1}
%}

\begin{document}

\title{icpc算法模板}
\author{Catch-22}
\date{\today}

\maketitle

\newpage

\tableofcontents

\newpage

\section{数学}


\subsection{求逆元}
注意考虑$x$是$mod$倍数的情况
\cppcode{math/inverse.cpp}


\subsection{扩展欧几里德算法}
bezout定理：设$a, b$为正整数，则关于$x, y$的方程$ax + by = c$有整数解当且仅当$c$是$gcd(a, b)$的倍数。 \\
返回结果：$ax+by=gcd(a,b)$ 的一组解 (x, y)  \\
\indent 时间复杂度：$\mathcal{O}(nlogn)$
\cppcode{math/exgcd.cpp}

\subsection{BSGS}
find smallest non-negative $x$ s.t. $a^x = b \mod p$, or $-1$(assume $0^0 = 1$)
\cppcode {math/BSGS.cpp}

\subsection{筛法}
筛质数
\cppcode{math/getprime.cpp}
筛欧拉函数
\cppcode{math/phi.cpp}
筛莫比乌斯函数
\cppcode{math/getMu.cpp}

\subsection{分解质因数(预处理因子)}
\cppcode{math/decomposeFactor.cpp}

\subsection{组合数}
\begin{enumerate}
	\item $C_{n}^{m} = C_{n}^{n-m}$
	\item $C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$
	\item $C_{n}^{0} + C_{n}^{1} + \cdots +C_{n}^{n} = 2^n$
	\item $ lucas:\ C_{n}^{m} \equiv C_{n\ mod\ p}^{m\ mod\ p} * C_{n/p}^{m/p} $
\end{enumerate}

多重集组合数：

设$S = \{n_1 \cdot a_1, n_2 \cdot a_2, \cdots n_k \cdot a_k \}$是一个由$n_1$个$a_1$,$n_2$个$a_2$,$\cdots$,$n_k$个$a_k$组成的多重集。设$n = \sum_{i=1}^{k}n_i$，对于任意整数$r \leq n$，从$S$中取出$r$个元素组成一个多重集(不考虑顺序)，产生的不同多重集的数量为：
$$
C_{k+r-1}^{k-1} 
- \sum_{i=1}^{k}C_{k+r-n_i-2}^{k-1} 
+ \sum_{1 \leq i < j \leq k}C_{k+r-n_i - n_j-3}^{k-1}
- \cdots
+(-1)^k C_{k+r-\sum_{i=1}^{k}n_i-(k+1) }^{k-1} 
$$

多重集排列数：

多重集$S = \{n_1 \cdot a_1, n_2 \cdot a_2, \cdots n_k \cdot a_k \}$生成的排列是$\frac{(\sum_{i=1}^{k}n_i)!}{n_1 ! \cdot n_2! \cdots n_k !}$

\cppcode{math/combination.cpp}

\subsection{卡特兰数(catalan)}

\begin{itemize}
	\item 有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
   \item 一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
   \item 在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
   \item 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
  \item 一个栈（无穷大）的进栈序列为 $1,2,3, \cdots ,n $有多少个不同的出栈序列？
  \item n 个结点可构造多少个不同的二叉树？
  \item n 个 +1 和 n 个 -1 构成 2n 项 $a_1,a_2, \cdots ,a_{2n}$ ，其部分和满足 $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ 对与 n 该数列为？
\end{itemize}

$$
catalan(n) = C_{2n}^{n} - C_{2n}^{n - 1}
$$
$$
catalan(n) = \frac{C_{2n}^n}{n + 1}
$$

前几项 \{1, 2, 5, 14, 42, 132 ... \}

\cppcode{math/catalan.cpp}

\subsection{容斥原理}
$S_i$为有限集，$|S|$为$S$的大小（元素个数），则：
$$
| \bigcup\limits_{i=1}^{n} S_i | =\sum_{i=1}^{n} |S_i| - 
\sum_{1 \leq i < j \leq n}|S_i \cap S_j | 
+ \sum_{1 \leq i < j < k \leq n} |S_i \cap S_j \cap S_k | + \cdots 
+ (-1)^{n+1} | S_1 \cap \cdots \cap S_n | 
$$ 
\cppcode{math/inclu-exclu.cpp}

\subsection{数论分块}
考虑和式：
$\sum_{i=1}^{n}f(i) \lfloor \frac{n}{i} \rfloor$，由于$\lfloor \frac{n}{i} \rfloor$的值成一个块状分布，故可以一块一块运算。我们先求出$f(i)$的前缀和，每次以$[l, r] = [l, \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor]$为一块分块求出贡献累加到结果中。(常配合莫反使用) \\
常见转换：
\begin{itemize}
	\item $\lceil \frac{a}{b} \rceil = \lfloor \frac{a-1}{b} + 1 \rfloor$
	\item $a\ mod\ b = a - \lfloor \frac{a}{b} \rfloor * b $ 
\end{itemize}
\cppcode{math/block-on-number.cpp}

\subsection{M\"{o}bius反演}
$\mu$为莫比乌斯函数，定义为
$$ \mu(x)=\left\{
\begin{aligned}
	&1   \  \  \ \ \ n = 1  \\
	&0    \  \  \ \ \  n\text{含有平方因子}  \\
	&(-1)^k  \  \ k \text{为n本质不同的质因子个数} \\
\end{aligned}
\right.
$$
性质：
$$ \sum_{d|n} \mu(d)=\left\{
\begin{aligned}
	&1   \  \  \ \ \ n = 1  \\
	&0   \  \  \ \ \ n \neq 1 \\
\end{aligned}
\right.
$$
证：设 $n = \prod_{i=1}^{k}p_i^{c_i},
n^{\prime} = \prod_{i=1}^{k}p_i$ \\
那么$\sum_{d|n} \mu(d) = \sum_{d|n^{\prime}} \mu(d) 
= \sum_{i=0}^{k}C_{k}^i \cdot (-1)^i 
= (1+(-1))^k = 1$ \\
反演：\\
形式一：
$$f(n) = \sum_{d|n}{g(d)} \Leftrightarrow g(n) = \sum_{d|n}{\mu(d)f(\frac{n}{d})}$$
证：
$$
\sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right)=\sum_{d \mid n} \mu(d) \sum_{k \mid \frac{n}{d}} g(k)=\sum_{k \mid n} g(k) \sum_{d \mid \frac{n}{k}} \mu(d)=g(n)
$$
用$\sum_{d|n}g(d)$来替换$f(\frac{n}{d})$，再变换求和顺序。最后一步变换的依据：$\sum_{d|n}\mu(d) = [n=1]$，因此在$\frac{n}{k}=1$时第二个和式的值才为 。此时$n=k$，故原式等价于$\sum_{k|n}[n=k]\cdot g(k) = g(n)$ \\  
形式二：
$$f(n) = \sum_{n|d}{g(d)} \Leftrightarrow g(n) = \sum_{n|d}{\mu(\frac{d}{n})f(d)}$$



\subsection{高斯消元}
\cppcode{math/Gauss.cpp}

\subsection{Miller\ Rabin\ 素数测试}
\cppcode{math/mr-test.cpp}

\subsection{FFT}
\cppcode{math/fft.cpp}

\section{数据结构}


\subsection{(带权)并查集}
\cppcode{data-structure/DSU.cpp}

\subsection{Sparse Table}
时间复杂度$\mathcal{O}(1)$，空间复杂度$\mathcal{O}(nlogn)$ \\
静态区间查询可重复贡献信息，如“区间最值”、“区间按位和”、“区间按位或”、“区间 GCD”
\cppcode{data-structure/sparse-table.cpp}

\subsection{01Trie}
\cppcode{data-structure/01Trie.cpp}

\subsection{树状数组}
\cppcode{data-structure/fenwich-tree.cpp}

\subsection{线段树}
\cppcode{data-structure/SegmentTree.cpp}
扫描线：(面积)
\cppcode{data-structure/SegTree-Xray.cpp}

\subsection{可持久化线段树}
\cppcode{data-structure/persistentSegTree.cpp}
\cppcode{data-structure/persistentSegTree2.cpp}


\subsection{线段树合并}
\cppcode{data-structure/segtree-merge.cpp}
\cppcode{data-structure/segmentTree_merge_jiangly.cpp}

\subsection{DSU\ on\ tree}
\textbf{静态}统计树上\textbf{所有子树}具有某些性质的个数\\

$\mathcal{O}(n^2)$的方式：
\begin{enumerate}
	\item 递归每个子树，记录某种性质出现
	\item 退出子树时候清空cnt数组(一般用于记录性质啥的)，以免影响到其他子树的统计
	\item 这样对于父节点而言，就要重新统计这颗子树的性质
\end{enumerate}

\textbf{优化：}

我们发现，某个节点的最后一棵子树可以不用清空统计。这貌似是一个常数优化，但当我们将最后一棵子树改成重儿子的时候，可以证明这样的时间复杂度是$\mathcal{O}(nlogn)$的。

\textbf{流程：}

\begin{enumerate}
	\item 第一次dfsHson得到重儿子
	\item dfs中，先递归其所有轻儿子，最后递归重儿子
	\begin{minted}{cpp}
    for (auto v:G[u]) {
        if(v == fa || v == son[u]) continue;
        dfs(v, u, false);
    }
    if(son[u] != -1) {
        dfs(son[u], u, true);
    }
	\end{minted}

	\item calc当前点(u)以及其所有轻儿子(在calc中递归完成)
	\item 如果当前点是其父亲的轻儿子，消除影响(同样通过calc完成，calc传入一个影响val可正可负)
\end{enumerate}

\cppcode{data-structure/dsu-on-tree.cpp}

\subsection{树链剖分}
\cppcode{data-structure/HeavyPathDecomposition.cpp}


%\subsection{左偏树}
%支持操作(以维护最小值为例)：
%\begin{enumerate}
%	\item 找到最小值 $\mathcal{O}(1)$
% 	\item 删除最小值 $\mathcal{O}(logn)$
%	\item 插入一个值 $\mathcal{O}(logn)$
%	\item 合并两个堆 $\mathcal{O}(logn)$
%\end{enumerate}
%\cppcode{data-structure/leftish-tree.cpp}

\subsection{珂朵莉}
\cppcode{data-structure/ODT.cpp}

\subsection{CDQ分治}
\cppcode{data-structure/cdq-template.cpp}

\subsection{莫队}
普通莫队：
\cppcode{data-structure/Mo.cpp}
带修莫队：
\cppcode{data-structure/modifyMo.cpp}

\section{图论}
\subsection{spfa}
\cppcode{graph/spfa.cpp}

\subsection{dijkstra}
稀疏图dijkstra：
\cppcode{graph/dij1.cpp}
稠密图dijkstra：
\cppcode{graph/dij2.cpp}

\subsection{最小生成树}
\cppcode{graph/MST.cpp}
另外，对于完全图的$MST$问题，可以考虑使用$Boruvka$算法。我们要在$nlogn$或$nlog^2n$时间内求出每个连通块最小的连接的边，而这个边权一般可通过点权以一定方式求出。 通常不用直接写出，运用该思想求解。

\subsection{kruskal重构树}
\cppcode{graph/kruskalRebuildTree.cpp}

\subsection{二分图匹配}
二分图匹配的模型有两个要素：
\begin{enumerate}
	\item 节点能分成独立的两个集合，每个集合内部有$0$条边
	\item 每个节点只能与$1$条匹配边相连
\end{enumerate}
二分图最小覆盖模型特点是：每条边有$2$个端点，二者至少选择一个。 \\
k\"{o}nig定理：二分图最小点覆盖包含的点数等于二分图最大匹配数包含的边数。\\
图的最大独立集：点集$S$中任意两点之间都没有边相连。其大小等于$n -$最大匹配数。(n是二分图总点数)
\cppcode{graph/BipartiteMatch.cpp}


\subsection{强连通分量缩点}
时间复杂度$O(m+n)$，反向枚举scc\_cnt即是新图拓扑序。
\cppcode{graph/tarjan-scc.cpp}

\subsection{无向图的双连通分量}
桥：
\cppcode{graph/tarjan-eDcc.cpp}
割点：
\cppcode{graph/tarjan-vDcc.cpp}


\subsection{lca}
\cppcode{graph/LCA.cpp}

\subsection{2-SAT}
\cppcode{graph/twoSAT.cpp}

\subsection{基环树}
基环树的性质：点数等于边数；度数是点数两倍。一般题目中出现“从一个点到另一个点建一条边”，“N个点通过恰好N条双向道路连接起来，不存在任何两条道路连接了相同的两个点”等类似信息可以判定该图是基环树森林。以下是求基环树(森林)直径(和)代码
\cppcode{graph/pseudotree-diameter.cpp}

\subsection{树哈希}
\cppcode{graph/treeHash.cpp}

\subsection{dinic}
\cppcode{graph/Dinic.cpp}

\section{动态规划}

\subsection{背包}
\cppcode{DP/knapsack.cpp}

\subsection{期望dp}
\cppcode{DP/expDP.cpp}

\subsection{数位dp}
\cppcode{DP/digitDP.cpp}

\subsection{换根dp}
换根dp一般时间复杂度为$\mathcal{O}(n)$，需要对树处理得到大规模答案，如对每个点得到一个答案。
\cppcode{DP/tree-change-root.cpp}

\subsection{数据结构优化dp}
\textbf{1D/1D dp转移}

\subsection{斜率优化dp}

(待完善)

\begin{enumerate}
	\item 单调队列优化 
	\item 二分
	\item cdq分治
\end{enumerate}

\cppcode{DP/convex-hull-trick.cpp}

例：LIS计数
\cppcode{DP/data-structure-DP.cpp}

\section{字符串}


\subsection{字符串Hash}
\cppcode{string/stringHash.cpp}

\subsection{Trie}
\cppcode{string/Trie.cpp}

\subsection{KMP}
\cppcode{string/kmp.cpp}

\subsection{Z-algorithm}
\begin{itemize}
	\item 给出字符串$a, b$，求$a$的每个后缀与$b$的LCP： \\
	设$ \$ $为字符集外字符，求 $b+\$+a$的Z函数，则$a$的后缀$a[i..]$与$b$的LCP为 $Z(|b| + 1 + i)$ 。
	\item 求$s$的每个前缀的出现次数：\\
	求$s$ 的Z函数。对于每一个 $i$ ，如果 $Z(i)$ 不等于$0$，说明长度为 $Z(i), Z(i) - 1, \cdots , 1$ 的前缀在此处各出现了一次，所以求一个后缀和即可。在这个问题中一般令$Z(0) = |s|$。
	\begin{minted}{cpp}
for (int i = n + 1; i < 2 * n + 1; ++i)
    S[z[i]]++;
for (int i = n; i >= 1; --i)
    S[i] += S[i + 1];
	\end{minted}

	\item 求 $s$的所有border: \\
	KMP就可以，也可以用Z算法。求$s$的$Z$函数。对于每一个 $i$，如果 $i+Z(i) = |s|$ ，说明这个Z-Box对应一个border。（注：与KMP不同，这里只是求所有border，不是求所有前缀的border）
\end{itemize}

\cppcode{string/z-algorithm.cpp}

\subsection{AC自动机}
\cppcode{string/AC.cpp}

\subsection{SA}
$lcp(i, j)$表示后缀$i, j$的最长公共前缀(的长度)

$height$数组定义： 
$ht[i] = lcp(sa[i], sa[i - 1])$

性质：
$lcp(sa[i], sa[j]) = min\{ht[i + 1..j]\}$ \\
由此，求两子串(排名为$i,j$)最长公共前缀就转化为了$RMQ$ 问题(求$ht[i+1]$到$ht[j]$的最小值)。

本质不同的子串：$\frac{n*(n+1)}{2} - \sum_{i=2}^{n}ht[i]$

$ht$数组连续一段不小于$h$的区间长度代表长$h$的这个子串的出现次数

\cppcode{string/SA.cpp}

\subsection{SAM}

\begin{enumerate}
  \item
	SAM的总状态数不超过$2n-1$ ，当字符串形如$abbb...$  时取到上界  	
  \item
	SAM的总转移数不超过$3n-4$ ，当字符串形如 $abbb...bc$ 时取到上界
  \item 构建SAM的复杂度为$| \Sigma| n$ ， $\Sigma$ 为字符集。（瓶颈是复制节点，所以如果字符集过大，可以考虑用map代替数组）
  
\end{enumerate}

SAM的总转移数不超过  ，当字符串形如  时取到上界
构建SAM的复杂度为 ，  为字符集。（瓶颈是复制节点，所以如果字符集过大，可以考虑用map代替数组）

\cppcode{string/SAM.cpp}

\subsection{Manacher}
用$Manacher+hash$可以求出所有本质不同的回文子串(存hash值),时间复杂度$\mathcal{O}(|s|)$。但是不用于求每个本质不同回文子串出现次数相关统计，因为统计出现次数时，$while(l<=r)$中不可以$break$，复杂度$n^2$
	\begin{minted}{cpp}
    auto p = manacher(s);
    Hash hs(s); //or doubleHash
    set<ull> res; // ll when doubleHash
    for (int mid = 1; mid < p.size() - 1; mid ++) {
        //枚举回文子串的左右端点
        int l = (mid - p[mid] + 1) / 2, r = (mid + p[mid] - 1) / 2;
        while(l <= r) {
            if(res.count(hash.get(l, r))) break;
            res.insert(hash.get(l++, r--));
        }
    }
\end{minted}

\cppcode{string/manacher.cpp}


\section{其他}
\subsection{glibc内置函数}
\cppcode{others/builtin-functions.cpp}

\subsection{\_\_int128读写}
\cppcode{others/int128-read-put.cpp}

\subsection{大整数运算}
\cppcode{others/BigInt.cpp}

\subsection{整数二分}
\cppcode{others/binary-answer.cpp}

\subsection{单调栈}
\cppcode{others/monotoneS.cpp}

\subsection{单调队列}
\cppcode{others/monotoneQ.cpp}

\subsection{矩阵快速幂}
\cppcode{others/matrix-power.cpp}

\subsection{MEX}
\cppcode{others/mex.cpp}

\subsection{GospersHack}
生成$n$元集合所有$k$元子集的算法。这个算法复杂度与答案个数是同阶的，比暴力枚举$2^n$个数然后分别算$popcount$要好。
\cppcode{others/GospersHack.cpp}

\subsection{C++17-STL}
\cppcode{others/c++17-and-STL.cpp}

\subsection{pbds}

头文件：
\begin{minted}{cpp}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
\end{minted}

带有 find\_by\_order() ，order\_of\_key()的set和map 

代替 std::set<int>
\begin{minted}{cpp}
using tree = __gnu_pbds::tree<int, null_type, less<int>,
             rb_tree_tag, tree_order_statistics_node_update>;
\end{minted}

代替 std::multiset<int>
\begin{minted}{cpp}
    using tree = __gnu_pbds::tree<pair<int, int>, null_type, less<pair<int, int>>, 
           rb_tree_tag, tree_order_statistics_node_update>;
    // 插入时：insert({value, count++});
    // 查找时 lower_bound({value, 0});
\end{minted}

示例

\cppcode{others/pbds.cpp}

\subsection{一些结论}

\begin{enumerate}
	\item 维护区间加， 区间查gcd
	利用gcd(a, b) = gcd(a-b, b)  // 常用结论 \\
	考虑维护差分序列，则gcd(a[l], a[l + 1], ..., a[r]) = gcd(a[l], b[l + 1], .., b[r])
	\item
	  \subitem 一个序列的异或和小于等于数值和 $a+b=a \oplus b+2(a \& b)$
	  \subitem 一个序列的数值和和异或和奇偶性相同

	\item 一般估计因子数是 $\mathcal{O}(\sqrt{n})$，但这个上界是比较松的。1e18内的数最多有103680个因子，1e9内有1344个因子。另外1e9内不同的质因子只有 $2\ 3\ 5\ 7\ 11\ 13\ 17\ 19\ 23$ 这9个，可以在上面使用二进制枚举。

	\item 除法上取整： $(a + b - 1) / b$， 或者$ceil(a.0 / b.0)$
	\item $\sum_{k=1}^{n-1}{k \cdot k!} = n! - 1$
	\item 根号trick：
	若a[i] > 0, $\sum_{i=1}^{n} a[i] = n$,则a中不同的数只有$\sqrt{n}$种
	\item 排列的性质： $ max - min + 1 = len $
	\item 合法括号的充分必要条件：任意前缀的左括号数大于等于右括号数字 (catalan数)
	\item 多个点的LCA是其中dfs序最小和最大的两个点的LCA
	\item $\sum_{i = 1}^{n}\sum_{j = i + 1}^{n}(A_i + A_j)(B_i + B_j) = \sum_{i = 1}^{n}A_i \dot \sum_{i = 1}^{n}B_i + \sum_{i = 1}^{n}(n - 2)A_i B_i$等式右侧利用前缀和可以在$\mathcal{O}(n)$时间内完成
	\item 树上 $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f(i, j) $ (其中$f(i, j)$表示$i$点到$j$点的路径长度) 。 可以考虑每条边的贡献 为 $w[u] * siz[u] * (n - siz[u])$ 之和。
	\item 给定m种类的物品，每种的个数分别为$sz_1, ... , sz_m$，不同种类之间可以两两匹配，则最多的匹配数为：$sz_{mx} \leq tot - sz_{mx} ? \lfloor \frac{tot}{2} \rfloor : tot - sz_{mx} $ \\ 同理，一种线段覆盖问题：给定一些线段（带有长度），x轴上的每个点最多被两条线段所覆盖，那个这些线段最少能覆盖多长的x轴？\\
	最少覆盖长度为$\lceil \frac{sum}{2} \rceil $，或者如果有一条线段的和大于$\frac{sum}{2}$，则最少覆盖长度为这条线段的长度
	\item 
	\begin{minted}{C++}
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,abm,mmx,avx,avx2,
popcnt,tune=native")
	\end{minted}

	
\end{enumerate}




\end{document}