离线，忽略删除操作之后，为每次插入的数编号（不考虑值，仅考虑位置）。
用树状数组+链表可以确定每一个被插入的数的位置。
接下来维护序列，每一个位置有两个值： \((A_i,P_i)\) 。其中 \(A_i\) 为权值， \(P_i\) 为这一个值上次出现的位置。
由于查询操作只考虑不同的元素，即对于区间 \([l,r]\) ，我们只考虑其中 \(P_i<l\) 的部分。
如果一个位置还没有被加入序列，或者已经被删除，将其标记为 \(P_i=\infty\) 即可。用树状数组可定位 \(l,r\) 在重构序列中的位置。
此时，问题变成了单点修改，二维区间查询。
维护和，两个元素积的和，三个元素积的和即可处理操作1，操作5即数点。
动态二维数点可以通过分块或者树套树处理。
\(\sum_{i=0}^w \binom{w}{i}(t-A\cdot i)^n\)
\(\sum_{i=0}^T (X+A\cdot i)^n ()\)
\(x^n=\sum_{i=0}^n i! S(n,i) \binom{x}{i}\)
$$ F_W(x)=e{Ex}{i=0}^W (e{Ax}+e{Bx}-2)i2{W-i}) \ F_W(x)=e{Ex}2W{i=0}W (-1)^i \ F_W(x)=e{Ex}{i=0}^n (-1)^i ^W \ [x^n]F_W(x)={i=0}n [x^n]e{Ex}(-1)i ^W \ [x^n]F_W(x) [x^m]G_{T-W}(x) = \ {i=0}^n [x^n]e{Ex}(-1)i {j=0}^m [x^m]e{Fx}(-1)j \ W{T-W} \ {W=0}^T [x^n]F_W(x) [x^m]G{T-W}(x)= \ 2^T n! m!{i=0}^n [x^n]e{Ex}(-1)i {j=0}^m [x^n]e{Fx}(-1)j \ \ =2^T n! m!{i=0}^n [x^n]e{Ex}(e{Ax}+e{Bx}-2)i {j=0}^m [x^m]e{Fx}(e{Cx}+e{Dx}-2)j \ 设 f_i=x^n^i=_{j,k} (-2)^{i-j}[x^n] (e{Ax}+e{Bx})^j \ 设g_i=x^n^i \
\ $$
LOJ上的 \(n\leq 18\)
如果把仙人掌上的树边看做二元环，那么可以认为仙人掌就是由很多环嵌套在一起的结构
状压 \(dp\) ，300iq的题解里给出了状态，但是也只告诉了你状态。。。
令 \(f(i,S)\) 为 \(i\) 号节点为根，子树集合为 \(S\) 的方案数
令 \(g(i,S)\) 为 \(i\) 号节点为根，子树集合为 \(S\) 的方案数，并且强制根上只接了一个环
令 \(dp(u,v,S)\) 为钦定一个当前环的开头为 \(u\) ，环尾扩展到了 \(v\) ，当前包含 \(S\) 的方案数
由此得到转移为
\(f(i,S)\cdot g(j,T)(S\cap T=\empty)\rightarrow f(i,S\cup T)\)
\(dp(u,v,S)\cdot f(d,T)(S\cap T=\empty,(u,v)\in E) \rightarrow dp(u,d,S\cup T)\)
\(dp(u,v,S) ((u,v)\in E)\rightarrow g(u,S)\)
实际上涉及到很多计算重复，因此需要在转移过程中加入一些调整:
1.在转移环时，钦定的环开头节点下方不应该接有任何其他节点
2.转移1中 \(S,T\) 合并上来时，可以保证 \(S<T\) 来避免集合加入顺序的重复
3.当环长>2时，同一个环，同一个开始位置会由于环遍历顺序的不同被转移两次
对于这个问题我的解决方法是: 让 \(\frac{dp(u,v,S)}{2}\rightarrow g(u,S)\) ，然后把环长为2的部分加上去
转移过程中涉及到集合运算都是枚举子集，因此复杂度一个很松的上限为 \(O(n^33^n)\)
转移顺序不难解决，代码比较丑
1 |
|
前置知识：集合幂级数的 \(\ln ,\exp\)
同样上面的，一颗仙人掌可以看做若干 \(\ge 2\) 环，两两之间在某一个节点上相接构成
不妨先求出环的集合幂级数，枚举环上编号最小的点，然后走环，复杂度为 \(O(n^32^n)\) ，常数较小
接下来当然想到枚举环的交点 \(i\) ，将当前所有包含 \(i\) 的项取出，去掉 \(i\) 后求出 \(\exp\) ，然后放回去，就能计算相交在 \(i\) 上的方案
两部分复杂度均为 \(O(n^32^n)\)
1 |
|
令 \(dis_{u,s}\) 表示 在 \(\mod L=s\) 到达 \(u\) 的最小时间，其中 \(L\) 表示 \(u\) 所在环。
对于状态 \(dis_{u,s}\) ，考虑所有的边 \((u,v)\) 。
当 \(u,v\) 有一个不在环上时，转移可以分为：
当 \((u,v)\) 为一条环边时，则只需要考虑能否直接走环边。
当 \(u\) 和 \(v\) 都在环上时，可以将转移压缩为以下几种：
令 \(t\) 表示 \(v\) 下一个被占据的时刻，如果 \(t\) 时刻 \(u\) 没有被占据，则可以采取以下方式：
最后就可以跟在 \(v\) 环的守卫后面。
如果 \(t\) 时刻 \(v\) 被占据了：
令 \(t'\) 表示 \(t\) 时刻以后，下一个回到 \(\mod L=s\) 的时刻，用 \(t'+1\) 更新。
令 \(t''\) 表示 \(t'\) 时刻以后，下一个 \(v\) 被占据的时刻，再次检查能否用 \(1\) 中的方案。 此时由于要多留一轮，需要判断
根据题意模拟，得到一种浅显的贪心方法是: 每次选择能吃的最大的一个吃掉
如果用set维护，就能得到一个 \(O(n^2\log n)\) 的算法!
考虑用加速这个贪心:
设当前重量为 \(now\) ，目标是 \(des\)
每次找到存在 \(\ge now\) 的最小的一条鱼 \(nxt\)
那么这一次决策的目标就是吃最少的鱼让自己能够吃掉 \(nxt\) 或者直接达到 \(des\)
在达到这一次的决策目标之前，能够吃的鱼的集合都是一样的
那么就可以找到最短的一段以 \(now-1\) 为右端点的区间使得区间的和达到目标
发现每做一次决策之后，下一次吃一条鱼就会翻倍，所以只有 \(\log 10^{18}\) 次决策
那么考虑如何用数据结构维护这个目标
注意一个比较难维护的问题，每次决策之后，被吃掉的鱼应当暂时消失
暂时消失的问题，常见的思路可能是:可持久化 或者 删除之后存下来回撤
涉及到插入，删除，二分区间，删除区间和复原区间
可以用 \(\text{Splay}\) 或者非旋 \(\text{Treap}\) 维护这个问题
复原区间的过程可以写成一个伪平衡树合并的样子
非常慢
1 |
|
离线之后写，让每个位置只包含一个数会更好写
关于用线段树维护暂时删除的问题，有很多写法
1.强行标记，把被标记的节点全部存下来然后复原
条件是: 每个点都要被覆盖，且不能被两种覆盖，那么最后覆盖的情况一定是形如下图的
其中红色和黄色的点表示关键的覆盖点，其他点按照其所属的颜色可以选择放或者不放
那么考虑从上到下，依次对于每一层 \(dp\) 竖线的位置，那么有两种转移方法
1.保留上层竖线，两边空白位置的可行点用2的幂次乘进答案即可
2.将当前层的竖线右移，必须选择两个位置，其他位置依然按照2的幂次加入答案
直接转移是 \(O(n^3)\) 的，对于第2中转移应用前缀和优化即可做到 \(O(n^2)\)
1 |
|
给定一个长度为 \(n\) 的01字符串
烯烃不存在连续两个碳碳双键出现的情况，因此可以把原来的序列分成若干个01交替序列，相邻之间用多个0隔开，这些序列之间不会干扰
一个包含 \(n\) 个碳碳双键的交替序列加成 \(k\) 次的方案数为 \(\displaystyle \binom{n+k}{n-k}\prod_{i=1}^{k} (2i-1)\)
证明思路：
一共有 \(\displaystyle \binom{n+k}{n-k}\) 种可能的结束状态
且任何一个合法状态均有 \(\prod_{i=1}^m (2i-1)\) 种可能的构造方法
可以从0次操作开始向上归纳，对于一个 \(k\) 次操作的状态，合法的逆操作一定是一段 两端是0的极长的 交替序列，容易通过次数分析发现此时合法的极长交替序列就只有 \(2k-1\) 个，即完成从上层的归纳
按照这个式子，分治 \(\text{NTT}\) 即可
设 \(\displaystyle C(x)=\sum_{i=0}^{\infty} C_i\)
易知 \(xC^2=C-1\)
设 \(F_{n,m}=[x^m](C-1)^n,F_n(x)=(C-1)^n\)
知 \(F_n(x)=(C-1)^n=xC^2 (C-1)^{n-1}=x ((C-1)^{n+1}+2(C-1)^n+(C-1)^{n-1})\)
即 \(F_{n,m}=F_{n+1,m-1}+2F_{n,m-1}+F_{n-1m-1}\)
即 \(F_{n,m}=F_{n-1,m+1}-2F_{n-1,m}-F_{n-2,m}\)
进一步规约，得到答案的表达式
\(\displaystyle Ans_i=[x^n] (C(x)-1)^i [y^i] e^{\varphi}\)
其中 \(\displaystyle \varphi=\sum _{i\ge 1}2(i+1) \cdot (C(x)-1) y^i\)
\(\displaystyle \varphi=\sum _{i\ge 1}2(i+1) \cdot (C(x)-1) y^i\)
\(\displaystyle \int \varphi\ dy =\sum_{i\ge 1} 2(C(x)-1) y^{i+1}=\sum_{i\ge 2} 2(C(x)-1) y^i\)
\(\displaystyle \int \varphi\ dy = 2(C(x)-1) \frac{y^2}{1-y}\)
\(\displaystyle \varphi=2(C(x)-1) (\frac{y^2}{1-y})'=2(C(x)-1) \frac{2y-y^2}{(1-y)^2}\)
\(G_{n,m}\) 为 \(n\) 个白格， \(m\) 为总格数的权值
\(\displaystyle G_{n}(x)=(\sum_{i\ge 2} 2i x^i)^n\)
设 \(\displaystyle \varphi(x)=\sum_{i\ge 2} 2i x^i\)
\(\displaystyle \varphi(x)=2x(\sum_{i\ge 2} x^i)'=2x^2 \frac{2-x}{1-x}\)
\(G_n(x)=\varphi^n(x)\)
\(Ans_i\) 表示有 \(i\) 个白格的答案
\(Ans_i=\displaystyle \sum_j G_{i,j} F_{j,n}\)
Object Oriented Programing in C++
主讲内容：近似算法 / 随机算法，中间会插入 oop 部分。 ## Intro
相对误差的近似：
\(\alpha\) 近似：\(output \leq \alpha \cdot ans\) 的算法
\((1+\varepsilon)\) 近似：\(output \leq (1+\varepsilon) \cdot ans\) 的算法，算法的复杂度为 \(O(f(\frac{1}{\varepsilon}))\)，这里通常 \(\varepsilon \in [0.01,0.3]\)