[NOIP2022] 种花
题意
不太好描述，感性理解（
题意
一道计数类问题。不难发现 F 形只需要在 C 形的基础上在末尾伸出一小支就好了。所以我们先考虑 C 形的计数方案。
图形计数类一个基本的 trick 就是枚举拐点，因此我们考虑枚举下面这一行的拐点（也就是首个种花的位置）\((i,j)\)。令上面所有行对它的贡献为 \(k\)。那么这个拐点的最终贡献就是 \(sum[i][j]\times k\)，\(sum[i][j]\) 表示从 \((i,j)\) 开始最多能扩展多少位种花的位置。
考虑计算这个 \(k\)。根据之前的分析，\(k=\sum\limits_{l=las}^{i-1} sum[l][j]\)，\(las\) 表示从 \((i,j)\) 能向上扩展到的最后一个可以种花的位置。这两个东西都可以前缀和维护一下就好。
对于 F 形，我们只需要计算到 \((i,j)\) 为止有多少个拐点在这一列的 C 形，把它延伸到这一行就好。注意要先判断这个位置能不能种，不能种的话要清零。然后把目前的 C 形的贡献加上，再更新这个拐点贡献的 C 形，最后更新这个拐点对 \(k\) 的贡献。
[NOIP2022] 喵了个喵
题意
给你一个 \(n\) 个栈，和 \(k\) 种卡牌，每种卡牌都有偶数张。在将一种卡牌放进一个栈顶后，你可以做以下两种操作：
- 将栈顶的两种相同元素消去
- 选取两个栈底元素相同的栈，将这两个元素消去
求构造一种操作方案使得最后所有牌都能消除。
题解
不会实现所以先估着。
[NOIP2022] 建造军营
题意
选择一个点集和边集，要求切断任意一条不在边集中的边后都不影响点集中的点两两之间的连通性。求选择点集，边集的方案数。一种方案数是不同的当且仅当它选择这种点集和边集的搭配没出现过。
题解
由于只能切断一条边，所以在一个边双连通分量里面的所有点都是不受影响的。因此我们可以先求出边双连通分量，只看桥的那些边，这样就可以把图转化成树。
假设我们现在选的兵营分别在第 \(i\) 和第 \(j\) 个连通分量中，那么 \(i\) 到 \(j\) 的路径上的所有边都要选。因此状态不仅和当前枚举的是哪个点有关系，还跟这个点有没有选有关系。因此我们令 \(dp[i][0/1]\) 表示在 \(i\) 的子树内且点 \(i\) 里面有没有兵营的方案数。
考虑这个状态为什么能包含所有情况。我们令有兵营的点为关键点，根据虚树的求法可知，这些若干个关键点一定有一个公共的 lca。因此这个 \(dp[i][0/1]\) 中的 \(i\) 实际上是枚举这个最高的节点。
\(dp[x][0]=(2^{num[x]}-1)\times (\prod 2\times dp[v][0])(v\in son_x)\)，\(2\) 的意义是 \(v->x\) 这条边能不能选都行，这个显然。对于 \(x\) 的子树里面有军营的情况，还可以分成两种情况。一种是 \(x\) 这个点里面就有军营，这一种的贡献是 \(2\times dp[v][0]+dp[v][1]\)，同理，当 \(v\) 里面什么也没选的时候这条边可选可不选，里面选了的话这条边就一定选。另一种是 \(x\) 这个点里面没有军营，这一类的贡献是 \(\prod (dp[v][0]+dp[v][1])-\prod dp[v][0]\)。但实际上，我认为这个式子当且仅当我们定义 \(x\) 的子树包含它到 \(fa[x]\) 的这条边的时候方便处理。这里我并没有让 \(x->fa[x]\) 这条边包含在 \(x\) 的子树内，因此更方便的转移式是每次新增一个点时，\(dp[x][1]=dp[x][1]\times (dp[v][1]+2\times dp[v][0])+dp[x][0]\times dp[v][1]\)，前面是分类讨论在 \(v\) 之前已经有点有军营了，后面是分类讨论 \(v\) 是第一个有军营的点。这个实际上可以归类为一个 trick，如果要求必须有一个点选，我们可以分类讨论它是第一个选的点还是随便怎么选的点。
令 \(siz[x]\) 表示 \(x\) 这个点内有多少个小点，\(e[x]\) 表示 \(x\) 这个点内有多少条边。初始化 \(dp[x][0]=2^{e[x]}\)，\(dp[x][1]=2^{siz[x]+e[x]}-dp[x][0]\)。
总结
对于这类题，我们首先可以通过题的特殊性质简化题，或者看到特殊性质分想到此题可以用边双变成一颗树。然后在做树形 dp 的时候，可以先设出第一维，然后考虑转移还跟什么有关。对于转移式便需要用到分类讨论了。
[NOIP2021] 数列
题意
- 给出每个数对应的权值
- 需找出所有符合 \(S=2^{a_1}+2^{a_2}+...+2^{a_n}\) 二进制中 \(1\) 的个数不超过 \(k\) 的 \(a\) 序列。
- 求出所有符合条件的 \(a\) 序列权值积的和
题解
显然可得是计数 DP 。
对于一个序列 \(a\)，最终的结果会跟 \(S\) 二进制中 \(1\) 的个数有关（判断可行性），\(a\) 中的元素有关（求出权值）。
事实上，由于并不能保证序列 \(a\) 中所有元素互不相等，所以还需判断 \(S\) 中进位的个数。
于是设出状态：\(dp_{i,j,k,p}\) 表示目前已经讨论了 \(S\) 从低位到高位的前 \(i\) 位和 \(a\) 中的 \(j\) 个元素，此时 \(S\) 中有 \(i\) 个 \(1\)，需向下一位进位 \(p\)。
若序列 \(a\) 中有 \(t\) 个 \(i\) 元素，那么易得此时 \(S\) 中第 \(i\) 为应该是 \((t+p)\bmod 2\)，向下一位进位 \(\frac{t+p}{2}\)。
所以下一个状态以及转移应是：\(dp_{i+1,j+1,k+(t+p)\bmod 2,\frac{t+p}{2}}=dp_{i,j,k,p}\times v_i^t\times C_{n-j}^t\)
解释下组合数的意思，首先最表面看就是 \(n-j\) 个数中取出 \(t\) 个数。这里指由于已经确定了长度为 \(n\)的序列 \(a\) 中 \(j\) 个位置，剩下 \(n-j\) 个位置中有 \(t\) 个 \(i\) 元素，总的方案数就是 \(C_{n-j}^t\)。
统计答案时，\(S\) 最高维不会超过 \(a\) 中元素的最大值也就是 \(m+1\)，第二维同理也不会超过 \(n\)。
但是在 \(S\) 的第 \(m\) 位后还有可能进位，这时候还需处理一下第 \(m\) 位后 \(1\) 的个数。
（哇酷，自己打了一遍题解果真理解了很多）