T322034 宇宙级难题

一天ZRP突发奇想

他想到了 字符串 后缀自动机,SAM字典树,TrieAC 自动机KMP后缀数组,SA后缀树有限状态自动机哈夫曼,Huffman回文自动机 PAMManacher 算法 动态规划,dp 动态规划初步背包数位 dp区间 dp树形 dp插头 dp 搜索 广度优先搜索,BFS深度优先搜索,DFS剪枝记忆化搜索迭代加深搜索启发式迭代加深搜索,IDA\*Dancing Links随机调整 数学 信息论集合论线性规划插值拟阵杨表,杨氏矩阵 图论 Kruskal 重构树网络流图论建模图遍历拓扑排序最短路K 短路生成树平面图最小环负权环连通块2-SAT欧拉公式强连通分量,缩点Tarjan割点欧拉回路差分约束仙人掌二分图一般图的最大匹配最大流上下界网络流最小割费用流圆方树Dilworth 定理 计算几何 立体解析几何凸包叉积线段相交点积半平面交凸多边形的交离散化扫描旋转卡壳 树形数据结构 线段树并查集平衡树堆树状数组cdq 分治左偏树动态树Link-Cut Tree,LCT树套树可持久化线段树可持久化整体二分K-D Tree李超线段树吉司机线段树,segment tree beat线段树合并 博弈论 Nim游戏博弈树Nim 积 线性数据结构 莫队珂朵莉树,颜色段均摊,ODT前缀和向量栈队列分块st表差分链表 多项式 快速傅里叶变换 FFT快速数论变换 NTT快速沃尔什变换 FWT快速莫比乌斯变换 FMT 数论 原根素数判断,质数,筛法最大公约数,gcd扩展欧几里德,扩欧不定方程进制中国剩余定理,CRT莫比乌斯反演逆元Lucas 定理类欧几里得算法,类欧 启发式搜索 爬山法模拟退火遗传A\*算法 动态规划优化 降低维度,降维优先队列矩阵加速,矩阵优化斜率优化状态压缩凸完全单调性,凸单调四边形不等式 树论 点分治树上启发式合并树的遍历最近公共祖先,LCA树的直径哈夫曼树树链剖分RMQ虚树基环树笛卡尔树动态树分治 群论 置换Polya原理 组合数学 排列组合二项式定理康托展开鸽笼原理容斥斐波那契,Fibonacci卡特兰数,Catalan斯特林数,Stirling生成函数,GF拉格朗日反演 概率论 众数条件概率期望 线性代数 LGV 引理矩阵树定理矩阵运算矩阵乘法线性递推高斯消元线性基 微积分初步 极限导数积分定积分级数 其它技巧 暴力数据结构高精度倍增三分离散化分数规划哈希,HASH随机化位运算构造双指针,two-pointerAd-hoc根号分治模拟费用流分散层叠均摊分析分类讨论折半搜索, meet in the middle 单调数据结构 单调队列单调栈

输入一个数n

输出n

文件