八百万年没有写过做题记录了，主要还是因为暑假忘了，现在重新写一下。
- 带
*表示未做出，带^表示半做出。
*A [PA2021] Od deski do deski
这个题的难点在于设计状态。首先明确这道题不是区间 dp，因为不同的区间答案显然一致。所以考虑对每一个长度 dp。接下来进一步考虑，我们对于一个位置 \(i\)，选的数如果要合法，那么前面必然存在一个 \(a_j=a_i\)，且 \([1,j-1]\) 合法。
对于考虑之前贡献的题目，不难想到提前计算。设 \(f(i,j)\) 表示长度为 \(i\) 的序列，当前共有 \(j\) 种 \(a_x\) 满足上述合法要求，且 \([1,i]\) 合法方案数；\(g(i,j)\) 表示的是 \([1,i]\) 不合法方案数。按照上述过程转移即可。
B [TJOI2019] 甲苯先生的字符串
简单矩阵快速幂即可。
C [ABC213G] Connectivity 2
考虑正难则反，用总数减去两者不联通方案数。对于不联通方案数，可以枚举 \(1\) 所在联通块点集，并使其不包含 \(x\)，然后求出使这部分点集联通的方案数再乘剩下点集之间任意连边方案数即可。
至于怎样求使一部分点集联通的方案数，利用经典的图上容斥计数套路即可。
*D 某位歌姬的故事
首先考虑 \(m_i=2,A=2\) 怎么做。实际上就是说要在序列上选一些点，使得给定的每个区间内都有一个点。显然可以利用 dp，设 \(dp(i,j)\) 表示在前 \(i\) 个位置中选，且最后一个点选在 \(j\) 的方案数。转移按照 \(i\) 选不选的情况讨论即可。为了满足区间限制，我们对每一个 \(r\) 求出所有询问中最大的 \(l\)。当我们来到一个 \(r\) 时，就要将所有 \(j<l\) 的 dp 值赋为 \(0\)。
然后考虑正解。首先将区间离散化，变成若干个点。接着对每一个点求出包含他的询问中 \(w\) 的最小值，则最后这个点必然只能选 \(\le minw\) 的数，且最后也只能对 \(w=minw\) 的要求做出贡献。因此，我们实际上可以将所有要求按照 \(w\) 拆开，每一个 \(w\) 都有对应为他做出贡献的位置，这样问题就和上面一样了。
当然现在复杂度是 \(O(Q^2)\) 的，利用线段树优化上述 dp 过程，可以做到 \(O(Q \log Q)\) 的复杂度。
*E [ABC134F] Permutation Oddness
考虑将位置和数值拆开，然后就是对它们进行配对。配对问题的一种经典做法就是记录前面有多少个位置还没有配上，进而计算贡献。此题同理，设 \(dp(i,j,k)\) 表示考虑前 \(i\) 个数，数值和位置分别有 \(j\) 个位置没有配上（显然两者数量相同），怪异度为 \(k\) 的方案数。根据当前枚举到的数值和位置是向后配对还是向前配对转移即可。
F [JSOI2018] 潜入行动
简单树形背包。设 \(dp(i,j,0/1,0/1)\) 表示 \(i\) 子树内放了 \(j\) 个监测点，且该节点被 / 不被检测、放 / 不放监测点的方案数。
标签：方案,专题,联通,记录,位置,点集,考虑,dp From： https://www.cnblogs.com/dzbblog/p/18468571