双见到了山东的朋友们。又感觉我已经不再年轻了。
D1
爆力100+100+100=300，可惜我不会爆力。
杜爷认为难度是B<C<A。
A. light
原题luogu7163 COCI2020-2021 #2 Svjetlo。
树，每个点有一个0/1，给定初始状态，你需要选一条不一定简单的路径，翻转上面的状态，求变成全1最小路径长度。\(n\leq 5\times 10^5\)。
牛逼dp。设\(dp(u,0/1,0/1/2)\)表示\(u\)子树，操作之后\(u\)是0/1，端点有几个在\(u\)子树内。那么显然考虑加入儿子\(v\)时转移的代价 :
-
如果\(v\)最后是0，我们需要走\(u\rightarrow v\rightarrow u\)。
-
如果\(v\)
B. cuboid
原题luogu7164 COCI2020-2021 #1 3D Histogram。
两个长\(n\)的序列\(a,b\)，求一个区间，使得\(\min a\times\min b\times(r-l+1)\)最大，只需要求出最大值。\(n\leq 2\times 10^5\)。
直接分治。考虑如果两个\(\min\)都在同一边取得，那么另一边应该尽可能长，这是容易的。如果不在同一边取得，不妨设\(a\)在左边取得，那么合法的右端点就是一个区间(\(a\)限制为一个前缀，\(b\)限制为一个后缀)。设四个数组\(al,ar,bl,br\)表示懂的都懂(如\(al\)表示A Left suffix max)，那么此时答案是\(al_lbr_r(r-l+1)\)，其中\(a_l,l\)我们枚举一下，拆成\(al_lbr_r(r+1)-al_lbr_rl\)，那么问题就是求\((al_l,al_ll)\cdot(br_r(r+1),br_r)\)，爆力线段树维护凸壳就是3\(\log\)。为了砍\(\log\)，可以注意到从中间向左走，\((al_l,al_ll)\)
C. tree
原题luogu7172 COCI2020-2021 #3 Specijacija。
懒得写题意了。
我的做法是，离线部分比较好做，考虑类似于sa把lca拆成相邻叶子lca的min，然后先求出这些lca，问题变成求出查询点子树中一个叶子。从下往上扫，可持久化线段树即可。
又是数数。
反射容斥
从\((0,0)\)走到\((n,m)\)，不能碰到上下两条横线A,B。
容斥。答案就是总方案数\(-\)碰到A的\(-\)碰到B的\(+\)碰到AB的\(+\)碰到BA的\(-\)碰到ABA的……这里碰到ABA的方案数指的是
集训队作业2018 count
考虑卡笛尔树，区间\(\max\)位置同构当且仅当(按位置为第二关键字建立的)卡笛尔树同构，于是问题变成对卡笛尔树计数。考虑另一个限制对笛卡尔树有啥效果，发现按位置为第二关键字建立的卡笛尔树，一个点的左儿子\(<\)它，而右儿子\(\geq\)它，我们可以随便分配相同的值，所以主要问题是左链不能太长，也就是我们在计数每个点左链长度不超过\(m\)的二叉树个数，或者说左偏深度(根深度\(1\)，往左走权\(1\)，右\(0\))不超过\(m\)的二叉树个数。
可以写出gf \(F_m=zF_{m-1}F_m+1,F_m=\frac{1}{1-zF_{m-1}}\)。这是分式线性变换，所以容易知道\(F\)是有理分式，然后可以写出分子分母的递推式，然后可以大力解出通项，然后拉格朗日反演。比较震撼，参见 https://blog.csdn.net/ei_captain/article/details/105377160 。
简单做法是转成括号序列然后反射容斥。
未知来源题
求含有\(n,m\)个\(1,-1\)的序列，任何区间和的绝对值不超过\(k\)的序列个数。
拆前缀和，然后问题变成从\((0,0)\)到\((n+m,n-m)\)，中间最高点和最低点相差不超过\(k\)的路径数。枚举最高点高度，
zroi题
使用一个随机数生成器生成序列\(a_1,...,a_l\)，生成\(i\)的概率是\(\binom{m}{i}p^i(1-p)^{m-i}\)。给一个不超过\(n\)次的多项式\(f\)在\(0,...,n\)处的点值。设
\[g(a)=\sum_{0\leq b_i\leq a_i}f\left(\sum b_i\right)\]求\(g\)的期望膜\(998244353\)。\(n\leq 10^5,m,l,p<998244353\)。
考虑能不能直接拆一下，考虑多项式定理，发现不是很行。
考虑既然给的是点值，我们对所有情况计算\(\sum b_i=k\)的时候的贡献，发现直接设一个的是\(G\)，那么总的就是\([z^k]G^n\)，而
\[G=\sum_i z^i\sum_{j\geq i}\binom{m}{j}p^j(1-p)^{m-j}\]，此时答案就是
\[\sum f(i)[z^i]G^n\]。为了让它变得简单一点，考虑把\(f\)拆成下降幂，此时有
\[\sum i^{\underline{k}}[z^i]G^n=(G^n)^{(k)}(1)\]，而自然数处的点值转下降幂可以\(O(n\log n)\)，这个按定义展开然后换求和号你就会了。
现在问题是我们要算\((G^n)^{(k)}(1)\)，考虑积的高阶导法则
\[(fg)^{(k)}=\sum_{i=0}^k\binom{k}{i}f^{(i)}g^{(k-i)}=k![t^k]\left(\sum_{i\geq 0}\frac{f^{(i)}t^i}{i!}\right)\left(\sum_{i\geq 0}\frac{g^{(i)}t^i}{i!}\right)\]，后面的式子是因为前面是二项卷积。于是可以瞪一个幂的高阶导法则
\[(G^n)^{(k)}=k![t^k]\left(\sum_{i\geq 0}\frac{G^{(i)}t^i}{i!}\right)^n\]，于是
\[(G^n)^{(k)}(1)=k![t^k]\left(\sum_{i\geq 0}\frac{G^{(i)}(1)t^i}{i!}\right)^n\]。按\(G\)的定义爆力计算即可。
美团CodeM决赛 B
对所有\(k\leq m\)，求所有\(n\)个点的无根二叉树中所有叶子对路径点数的\(k\)次方和。\(n\leq 10^7,m\leq 300\)。
考虑一个点会被左右子树之间的路径经过，用\(z\)表示点数而\(t\)表示所求的幂次，设答案是\(F\)，则有\(F=z()\)
单位根反演
某一天和空的讨论了一下，认为单位根反演就是\([z^0]z^n\bmod{z^k-1}=[k\mid n]\)，然后左边crt一下。
loj6271 生成树求和 加强版
每一位是独立的。考虑枚举每一位的值，如果一位的总和是\(s\)而值是\(k\)，我们就知道\(3\mid s-k\)，单位根反演得到一棵树的权值是
\[\sum_{i=0}^2[3\mid s-i]=\frac{1}{3}\sum_{i=0}^2\sum_{j=0}^2\omega_3^{-ij}\omega_3^{js}\]那么也就是一条边的权值是\(\omega_3^{jv}\)这样的，算即可。然而\(\omega_3\)不存在，强行扩域即可。
白给恒等式
\[\sum_i\sum_j\binom{n}{i}\binom{n}{j}(-1)^{i+j}\int_0^{-i}x^{n-1}(x+i-j)^{n+1}\mathrm{d}x\]看起来是什么先大力积出来，然后\(i,j\)都是高阶差分，最后只剩下很少项，爆力算就行了。
D2
爆力100+100+60=260，但是看起来只有八先生打到了?
A. block
数点题。
B. sbt
序列和一个\(k\)，支持单点修改，每次修改后查询所有长\(k\)的区间，最大值和次大值(非严格)的和的最大值。\(n\leq 10^6,q\leq 10^5\)。
线段树分治，然后线段树。
C. ntt
中文名 逆天题（
设从\(1,...,nm\)中选若干个数，总和膜\(n\)为\(k\)的方案数为\(f_k\)，求\(\sum f_k^2\)。\(n,m\leq 10^{18}\)。
容易写出\(f\)的gf
\[\left(\prod_{i=0}^{n-1}(1+z^i)\right)^m\bmod{z^n-1}\]设取膜前面的东西是\(F^m\)，那么单位根反演一下，可以直接写出答案的式子
\[\frac{1}{n^2}\sum_{k=0}^{n-1}\left(\sum_{i=0}^{n-1}\omega_n^{ik}F^m(\omega_n^i)\right)^2\]把卷积大力展开，会得到这个
\[\frac{1}{n^2}\sum_{k=0}^{n-1}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\omega_n^{(i+j)k}F^m(\omega_n^i)F^m(\omega_n^j)\]注意到\(k\)是一个单位根反演，于是变成
\[\frac{1}{n}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}[n\mid i+j]F^m(\omega_n^i)F^m(\omega_n^j)\]因为\(i\)只出现在\(\omega_n\)的指数上，我们修改\(i\)的范围为\(1,...,n\)，就得到
\[\frac{1}{n}\sum_{i=1}^nF^m(\omega_n^i)F^m(\omega_n^{-i})\]接下来我们考察\(F(\omega_n^i)F(\omega_n^{-i})\)。它就是
\[\begin{aligned} &\prod_{j=0}^{n-1}(1+\omega_n^{ij})(1+\omega_n^{-ij})\\ =&\prod_{j=0}^{n-1}(2+\omega_n^{ij}+\omega_n^{-ij}) \end{aligned}\]然后我们就卡住了。
____说的好，当你不知道干什么的时候就打个表。打表可以发现这个式子总是整数，同时可以发现对于一些\(i\)这个值是相同的，进一步可以发现对于所有\(i\perp n\)的\(i\)，这个式子是相同的。注意到当\(i\perp n\)的时候，\(\omega_n^i\)是本原单位根，而本原单位根的效果都是枚举了一圈，所以它们确实都是\(F(\omega_n)F(\omega_n^{-1})\)，继续打表可以知道这个式子在\(n\)为奇数时是\(4\)，偶数是\(0\)。
然后考虑\(i\not\perp n\)会发生什么。设\(d=\gcd(i,n)\)，那么\(\omega_n^i=\omega_{\frac{n}{d}}^{\frac{i}{d}}\)，于是有
\[\prod_{j=0}^{n-1}(2+\omega_{\frac{n}{d}}^{\frac{i}{d}j}+\omega_{\frac{n}{d}}^{\frac{i}{d}j})\]发现它是枚举了\(d\)圈，所以我们知道它就是\(\left(F(\omega_{\frac{n}{d}})F(\omega_{\frac{n}{d}}^{-1})\right)^d\)。整理一下我们就得到了答案 :
\[\sum_{i=1}^n[\frac{n}{\gcd(n,i)}\text{ is odd}]4^{\gcd(n,i)m}\]枚举\(\gcd\)然后莫反即可，最后需要pr分解一下然后做一个高维前缀和，复杂度\(O(n^{\frac{1}{4}}+d(n)\omega(n))\)。
数据结构基础
一般来说我们会考虑一些运算。列举一些优秀性质。
交换。
结合。
可差分/可逆 : 比如+，xor，行列式非零的线性变换。
幂等 : 比如max。
封闭 : 比如max，kth。
可合并 : 比如+，max，rank。
可插入 : 比如众数，小z的袜子。
带插入kdt
使用二进制分组。
Ynoi。
关于 Ynoi
lxl 自己出的/买的数据结构题集合，大部分比较有趣
中文读音为“由乃 OI”，neta 自《未来日记》中的我妻由乃
其中一部分是“大分块”，命名为“第 X 分块”，neta 自《末日时在做什么？有没有空？可以来拯救吗？》（末日三问），是一些 lxl 认为重要/有纪念意义的题。Ynoi 中从 2018 开始往后的都是大分块（但是 2077 不是）。按照末日三问，一共有十五个大分块。但是目前没有全部公开。一般来说，大分块作为最重要的题，会进行比较极限的卡常，并且配上稀奇古怪的 gal/番介绍。
随着时间流逝，Ynoi 题库可能会有一些小变化，即使大分块也一样。
另外，2077 lxl说是难以卡掉爆力和乱搞的题。
TB2 弱化版 加强版
区间\(>x\)的减\(x\)，区间查询一个数出现次数。\(v\leq 10^9\)，复杂度\(n\sqrt{n\log n}\)。
考虑把值域分成\([1,x],[x+1,2x],[2x+1,\infty]\)，中间那一块会折半，右边可以直接平移，平衡树维护即可。
或者把值域分成\(\log\)块，每一块开一个序列线段树。
TB10
分散层叠。
这个trick说的是，静态的分散层叠是有若干个序列，你需要依次在上面二分，而动态的是序列支持修改。此时在序列们上面建立线段树，然后每个点取左右儿子各\(\frac{1}{3}\)归并起来。
D3
爆力100+60+50=210。
A. random
单点修改，维护st表，随机数据。
发现变化量期望\(\log\)，直接从\(f(0,i)\)出发爆力递归地改就结束了。
B. tree
牛逼题。树，根是\(1\)，叶子的权值是\(0,...,n\)中的某个值，内部结点的权值是儿子们的\(\operatorname{mex}\)。对于所有叶子的取值方案(如果有\(c\)个叶子，方案数应该是\((n+1)^c\))，求\(1\)的权值为\(0,...,n\)的方案数。\(n\leq 200\)。
容易想到容斥，然后这个容易做到\(O(2^k\operatorname{poly}(n))\)，其中\(k\)是这个点的最大可能权值。这玩意没法做到多项式复杂度，因为想一想发现可以归约积和式。
发现叶子在这里很恶心。考虑非叶子的儿子的最大可能权值，设为\(t\)，那么我们在
然后另一个显然的做法是状压dp，这个复杂度也是\(O(2^k\operatorname{poly}(n))\)，其中\(k\)是这个点的儿子个数。
C. gen
状压dp神秘优化集大成者。\(n\times n\)的棋盘，每个位置有一个01变量\(a\)，一个权值\(b\)。给出所有\(b\)
joi 2022 final 沙堡2
考虑枚举一个子矩形，看它能不能有一条合法路径。发现这个一定是排序之后从大到小走，所以也就是rank相邻的两个格子都需要相邻。
考虑一点更局部的性质，注意到一个格子总是向周围权值比它小的格子中最大的那个走。这个方向只和它在子矩形的哪个边界上或者在内部有关。合法当且仅当没有入度没有出度的点各有最多一个。
考虑在短边上枚举一个区间，不妨设它是纵轴，然后问题就变成横轴上一维的了。然后大力dp即可，设\(dp(i,0/1,0/1,0/1)\)表示前\(i\)列，第\(i-1\)列不选/选，第\(i+1\)列不选/选，没有/有一个没有出度的点的方案数，复杂度\(O(n\sqrt{n})\)。
uoj578 校验码
考虑这个指数除以\(2\)下取整说的就是提平方因子，我们可以用\(\mu^2=1\)描述提光了平方因子。然后题目里面说这个东西积性，所以对\(i,j\)分别提完平方因子之后，剩下的部分乘起来，每个素因数次数不超过\(2\)。如果\(\leq 1\)，那么就没有贡献了，所以我们相当于要求一个\(\gcd^c\)了。反演即可。剩下的等我推一推。
题目难度提升
爆力怎么做，考虑逐位二分，我们
cf1687 E. Become Big For Me
考虑这个就是每个素因数次数的最小值和次小值加起来，然后我们就考虑kth min-max容斥，但是这个操作数是指数级。
考虑我们找到每个素数次数的最小值和次小值在哪取得，就可以把集合大小缩到很小。我们首先随便选一个数\(x\)，把它分解掉，然后对每个数求这个素数的幂次，取其中最小的和\(x\)一起形成一个集合，注意到不同素因数个数最多只有\(7\)，所以我们最多选\(8\)个。然后把这些数都扔掉，再跑一遍，得到\(16\)个数，但是很遗憾这个操作数好像飞了恰好一点。考虑怎么砍下来，发现如果每个素因数都取了一个最小的，那么\(x\)就可以扔掉了，于是只剩下\(14\)个数，就过了。
uoj76 懒癌
uoj431 time map
注意到从上往下走and会增加\(\log\)次，所以这个查询的过程分成\(\log\)段这样的。直接倍增，用线段树维护and和，复杂度\(O(q\log^3 n)\)，其中那个线段树是一个\(\log\)的，懒得区分\(n,v\)了（
考虑如何砍一个。发现我们倍增的时候一个端点是固定的，所以可以直接在线段树上二分另一个端点，就无敌了。
uoj425 strings
考虑折一折，我们枚举前\(k\)位，对每个串看后\(n-k\)位所有情况下它是否合法，压成一个bitset。
uoj327 去月球
显然按任意顺序贪心选择是正确的。
恐怖故事是，这个信息可以差分。我们要查\([l,r]\)，那么可以查\([1,r]\)，然后把\([1,l-1]\)倒着接到前面，这样\([1,l-1]\)就自己撞自己撞没了，答案增加\(l-1\)。于是设\(f(l,r)\)表示一个区间消完之后剩下的部分，乘法表示串接并继续消掉，那么我们有\(f(l,r)=f^R(1,l-1)f(1,r)\)。注意到两个内部已经消完的序列，合并它们的时候就是求lcp，也就是说这里我们会撞掉\(f(1,l-1)\)和\(f(1,r)\)的lcp，所以建立这些前缀的trie然后求lca即可，可以做到\(O(n)-O(1)\)。
uoj237 shortcut
考虑枚举左端点，那么右端点也是单调右移的，考虑
D4
爆力100+100+100=300。
A. tree
别乳卡题。
B. array
插值，树dp题。很遗憾，不会插值，也不会树dp。
C. string
压缩sam题。等我学在线线性构造压缩sam。
计算复杂性理论。
字符集是有限集。
语言 : 字符串的集合。图灵机最后停止于一个accept/reject状态，表示输入是否属于某个语言。显然每个图灵机对应一个语言。
一个图灵机识别一个语言 : 如果停机，则结果正确。
一个图灵机决定一个语言 : 识别，并且必然停机。
定理 如果一个图灵机\(A\)在\(f(n)\)时间内停机，那么通用图灵机可以在\(O(f(n)\log f(n))\)内模拟它。
定理 有一个集合\(A\)，定义它的幂集\(\mathcal P(A)\)为\(A\)所有子集组成的集合，则\(A,\mathcal P(A)\)不等势。
证明 考虑如果存在一个从\(x\in A\)到\(S\in\mathcal P(A)\)的双射\(f\)，那么定义\(T\)是所有满足\(x\not\in f(x)\)的\(x\)组成的集合，考虑\(T\)所对应的元素\(t\)。注意到如果\(t\in T\)，那么根据\(T\)的定义应该有\(t\not\in T\)，否则应该有\(t\in T\)，于是导出矛盾。
定理 有无限个不可识别语言。
证明 图灵机和整数是双射，而语言和整数的幂集是双射。
定理(UC) 不存在一个图灵机可以决定 输入一个图灵机，判断它在它自己上是否停机。
证明 考虑如果有这么一个图灵机\(A\)，我们构造一个新的图灵机\(B\)，它先直接把输入喂给\(A\)，然后如果\(A\)返回accept，则跑一个死循环，否则返回accept。那么如果\(A\)认为\(B(B)\)停机，也就是\(A(B)\)返回accept，那么\(B(B)\)就其实会跑一个死循环，矛盾；如果认为\(B(B)\)不停机，也是一样的。
不可计算性的归约
如果A可以转化成B，转化过程是可计算的，那么
-
如果B不可计算，A也不可计算
-
如果A可计算，B也可计算
。
定理 不存在一个图灵机可以决定 输入一个图灵机，判断它是否不会接受任何输入。
证明 如法炮制，如果存在这么一个图灵机\(A\)，我们构造\(B\)，它在\(A\)认为\(B\)不接受任何输入的时候返回accept，在\(A\)认为\(B\)接受某些输入的时候返回reject。
定理 不存在一个图灵机可以决定 输入两个图灵机，判断它们是否识别相同的语言。
证明 如法炮制，如果存在这么一个图灵机\(A\)，随便找一个\(B\)，我们构造\(B^\prime\)，它在\(A\)认为\(B,B^\prime\)不相同的时候跑一个\(B\)，在\(A\)认为\(B,B^\prime\)相同的时候跑一个\(B\)然后取反。
预测图灵机的计算结果大概率是不可计算的。
定义复杂度类是一个语言的集合。\(\mathrm{DTIME}\)指的是可以计算的语言，\(\mathrm{DTIME}(T(n))\)指的是可以在\(O(T(n))\)内决定的语言。
定理 如果\(f(n)\log f(n)=o(g(n))\)，则\(\mathrm{DTIME}(f(n))\subsetneq \mathrm{DTIME}(g(n))\)。
证明 考虑构造一个可以在\(O(g(n))\)内计算而不能在\(O(f(n))\)内计算的语言。考虑如果一个语言可以在\(cf(n)\)内计算，其中\(c\)是常数，我们考虑计算它的图灵机\(M\)，构造一个图灵机\(U\)，它的输入是一个图灵机\(M\)，如果\(M\)在\(cf(n)\)步内停机，则输出与\(M\)相反，否则输出\(0\)。
定义\(\mathbb{P}\)是多项式时间内可以计算的语言。
定义非确定性图灵机是一个状态可以有多个转移的图灵机，它走到每一步的时候会同时尝试所有转移，如果有至少一种返回accept，则返回accept，否则返回reject。当我们说图灵机，默认是确定性图灵机。
\(\mathrm{NTIME}\)是非确定性图灵机可计算的问题。定义一个非确定性图灵机的步数是步数最多的分支的步数，定义\(\mathrm{NTIME}(T(n))\)是非确定性图灵机可以在\(O(T(n))\)内决定的语言。
定义\(\mathbb{NP}\)是非确定性图灵机可以在多项式时间内决定的语言。
等价定义是存在一个图灵机，它接收我们要判断的串和一个串 证据，并在多项式时间内判断这个 证据 是否可以证明输入属于我们要决定的语言。如果要么在多项式长度内存在一个证据，要么输入不属于我们要决定的语言，那么这个语言是\(\mathbb{NP}\)的。
D5
爆力100+100+100=300。
A. grid
模拟。需要讨论一下。
八先生葬身于此痛失阿克/hanx
B. posion
原题bears and juice。
C. number
给\(p\)，求\(0\leq a,b\leq p(p-1),a^b\equiv b^a\pmod{p}\)的\(a,b\)对数。\(p\leq 10^{12}\)。
注意到底数膜\(p\)而指数膜\(p-1\)，\(p\perp p-1\)所以两部分是独立的。考虑这是相等的对数，我们尝试求每一种的个数，问题变成
\[\sum_{k=0}^{p-1}\left(\sum_{x=0}^{p-1}\sum_{y=0}^{p-1}[x^y\bmod{p}=k]\right)^2\]边上好像差了一点，不过是容易计算的。考虑原根，重设\(x\)为\(g^x\)，条件变成\(xy=\ln k\)，转而枚举\(\ln k\)，得到
\[\sum_{k=0}^{p-1}\left(\sum_{x=0}^{p-2}\sum_{y=0}^{p-1}[xy\bmod{p-1}=k]\right)^2\]边上好像差了一点，不过是容易计算的。考虑固定一个\(x\)，\(y\)会转圈圈，转\(\gcd(x,p-1)\)圈，如果\(x\mid k\)则贡献\(\gcd(x,p-1)\)，否则没有贡献，所以答案就是
\[\sum_{k=0}^{p-1}\left(\sum_{x\mid k}^{p-2}\gcd(x,p-1)\right)^2\]然后就结束了，展开平方，换个求和号之后直接求即可。
np-hard
所有np问题都可以多项式时间归约到的问题称为np-hard问题。
如果一个问题np-hard，并且本身也是np的，那么称为np-complete。
sat
证明sat是np-hard的。
考虑从sat构造一个通用图灵机。
考虑我们设出每个时刻纸带的状态。一个时刻到下一个时刻的转移正确，当且仅当它每一步的变化都符合转移函数，并且没有不该变的位置变了这样的。然后就结束了。
3-sat
发现sat是一堆形如 至少一个是1 的条件，那么考虑怎么缩减一个条件中的变量个数，考虑把它拆成前两个和后面的，加入一个变量表示前两个是不是至少一个是\(1\)，如果不是那么后面至少一个是\(1\)。为什么不能归约到2-sat?因为加入一个删除一个相当于啥也没做。
最大独立集
给一张图，判定有没有一个大小\(\geq k\)的独立集。
考虑归约到3-sat。考虑我们直接对每个条件建\(7\)个点表示所有可能的合法情况，然后冲突的连边即可。
最小点覆盖
考虑 一条边端点至少有一个 反过来就是 一条边端点至多有一个，所以求最大独立集然后取反即可。
01整数线性规划可行性
显然强于sat。
精确覆盖
强于sat。
子集和
强于精确覆盖。
conp
非确定性图灵机定义为，只要有一个分支返回accept整体就返回accept。对应地，有一个分支返回reject整体就返回reject的反的非确定性图灵机能解决的问题是conp的。
结论 \(\mathrm{P}=\mathrm{NP}\cap\mathrm{coNP}\)。
D6
爆力100+100+60=260。
A. transport
圆方树上换根dp/fn
B. hunt
有趣题。原题cf843D。
考虑转化成一个可以线性解决的最短路。这样的最短路也就是到每个点的最短路长度都在\(O(n)\)内的最短路，或者是dag的最短路。转化的方法看起来是瞪或者重赋权重。发现直接按上一轮最短路重赋权重，得到的每个点的最短路长度都在\(n\)以内，实际上此时最短路的意义是最短路的增量。跑即可，复杂度\(O(q(n+m))\)。
C. field
有趣题。原题
cf dp题。
cf1408G
也就是一条 集合间的边 比所连两个集合内的边都要大。
考虑从小到大扫值域，考虑所有边权\(\leq x\)的边，我们搞的一个集合必然是某个\(x\)所导出的图中的一个是团的连通块。注意到连通块会发生\(n-1\)次合并，一共只有\(O(n)\)个。把它们的合并树建出来，问题变成选择一些点，使得没有一个是另一个的祖先，背包即可。
cf1383E
考虑操作之后每个数是一个区间的\(\operatorname{or}\)。
考虑如果至少有一个\(1\)，我们总不需要合并两个\(0\)。
考虑什么情况下一个结果序列是合法的，按照\(1\)分成若干段，发现操作的效果是吃掉了\(0\)或者在一段被吃空之后把它的\(1\)也杀了。
考虑贪心匹配所有的\(0\)，设\(dp(i,j)\)表示结果序列前\(i\)段，匹配了原序列前\(j\)段的\(0\)的方案数。直接做复杂度\(O(n^4)\)。转移大概是说，枚举结果序列第\(i+1\)段多长，然后从\(j\)往右找到第一个足够长的段。可以在单调栈上双指针做到\(O(n^3)\)，然后发现这个东西也可以直接在单调栈上维护做到\(O(n^2)\)。
发现记\(i\)啥用没有，所以就\(O(n)\)了。
cf1372E
考虑我们希望让\(1\)更集中，因为如果\(a<b\)，我们知道\(a^2+b^2\leq (a-1)^2+(b+1)^2\)，于是如果一列没有满，我们可以调整一下让某一列满。枚举这一列，然后分成两边，发现两边分别还有一列是把还能填的位置都填了，于是这是一个区间dp。
cf1366G
容易想到\(n^3\)，也就是设\(dp(i,j)\)表示前\(i\)个操作删掉多少个可以匹配目标串前\(j\)个。转移有删，不删，等这个字符被删掉。发现如果等的话，等的过程中必然不会删，不然等价于直接删这一个。最小等到哪里可以用一个栈跑出来，于是复杂度\(O(n^2)\)。
cf1342F
设\(dp(i,S,j)\)表示前\(i\)组，用了\(S\)里面的，第\(i\)组里面最后都加到了一开始位于\(j\)位的数。复杂度\(O(3^nn^2)\)。
cf1326F2
lyh : 能听懂吗?
不能。
lyh : 好。那我们讲下一题。
cf1299D
考虑这个条件是啥，发现就是xor不出\(0\)。
注意到线性基很少，据说有374个，所以拿着这个dp即可，也就是说设\(dp(i,j)\)表示前\(i\)个环，。
cf1292F
cf1290F
也就是正的\(x\)和负的\(x\)和相等，正的\(y\)和负的\(y\)和相等，对这个进行数位dp。
cf1286F
考虑我们需要对\(k\)个数用\(k-1\)次操作才有用。问题变成如何判断一个集合能不能少用一次操作。注意到一个集合操作\(k-1\)次，剩下的一个数的可能值是一个区间，所以结束了。恐怖故事是，打表发现这个不是一个区间，而是一个公差\(2\)的等差数列。
cf1279F
\(n^2\)是容易的。
考虑转化成 最大化小写字母个数 或者 最小化大写字母个数。凸的，wqs二分即可。
cf1276D
序列和方案是双射。
直接树dp。一个点有四种情况 : 没被删，在父边之前被删，在父边被删，在父边之后被删。转移考虑
-
如果没被删，儿子们都需要在父边之前被删。
-
如果被删了，那么儿子们都需要在
D7
平均分300。阿克了五个人。
A. jump
简单dp，前缀和优化。
B. flow
有源汇网络，每条边有一个容量和一个流量，源是\(1\)汇是\(n\)，保证源没有入边汇没有出边。但是每个点出入可能不相等，边的流量也可能超过容量，每次可以把一条边流量或容量增大或减小\(1\)，求让网络合法的最小操作次数。\(n,m\leq 100,v\leq 10^4\)。
模板 辅助网络。这个名字是我自己起的。如果你居然真的有兴趣，可以去看tricks那一篇。
C. tree
树，加一条边变成基环树，最大化基环树上的简单路径数。\(n\leq 5\times 10^5\)。
容易转化成 找一条链，把链上的边删了，最小化每个连通块大小的平方和。
考虑dp，设\(dp(u)\)表示选一条\(u\)出发到子树内某个点的链，不考虑\(u\)所在连通块的最小平方和。转移是容易的。
考虑如何统计答案。如果答案是祖先-后代链，可以直接在转移\(dp(u)\)的时候考虑\(u\)所在连通块并计入答案。如果答案不是祖先-后代链，考虑枚举lca的两个儿子，然后发现答案变成了一个奇怪的东西，可以枚举一个儿子，用李超树维护另一个，复杂度\(O(n\log n)\)，看起来可以单调队列维护凸壳做到线性。
cf1225G
考虑每个数的贡献，它必然是\(\frac{a}{k^e}\)这样的。结论是，只要贡献之和为\(1\)，就存在一个操作方案。做法是，按照除的次数从大到小，每次选最大的两个合并，合并之后如果是\(k\)的倍数则除一个\(k\)并让\(e:=e-1\)即可。
考虑扫\(e\)，设\(dp(i,S)\)表示\(S\)中的数\(e\)非零，
cf1197F
我们要合并它们，就是求sg值。好消息是，sg值很少，所以可以直接爆力dp，矩阵快速幂。然后卷即可。
cf1194G
先枚举\(x^\prime,y^\prime\)，然后问题是查询有多少个\(k\)满足\(k\leq \frac{n}{\max(x^\prime,y^\prime)}\)，且\(kx^\prime,ky^\prime\)十进制下分别包含\(x^\prime,y^\prime\)。
注意到这个很小，直接状压高精乘单精即可。
有一个小问题是\(\frac{3}{2}\)和\(\frac{6}{4}\)是一样的这样的，所以我们需要钦点一下\(x^\prime\perp y^\prime\)，然后直接爆力记录每一位有没有出现过，这样如果我们实际上要算\(ax^\prime,ay^\prime\)也可以算了。
cf1188D
看起来很困难。考虑我们对最后的数数位dp，然后操作次数就是用最后这个数减每个数，把popcnt加起来。考虑问题是哪些数会退位，发现按低位排序之后一个后缀会退位，所以就结束了。
cf1152F2
考虑扫值域，每次插入一个数，注意到第\(i\)个点能不能选只和\(i-1,...,i-m\)里面的点有关，状压之后矩阵快速幂即可。
cf1146H
能连成五角星，等价于这五个点的凸包包含所有五个点。转转转dp即可。
cf1142D
如果不知道干什么你就打个表。发现这个限制是以\(11\)作为循环节长度的。