神秘计数DP
今天某个学校的任务是
观前提示
这个题单不是自己整理的
这个题单几乎所有题目都是理解题解后才做的，不看题解这个蒟蒻真不会
压缩 毛巾 题解 笔记
- CF294C Shaass and Lights 提交记录 这道题自己做的
首先1\sim a_1-1 和a_m+1\sim n 只有一种方案先算所有排列再**除以**顺序不合法的方案 吃了几发罚时竟然是没排序 - 设 $f_i$ 为中间空了 $i$ 格的点灯方案数 - $f_1=1 -
- CF1753C Wish I Knew How to Sort 提交记录
这道题并不是特别懂
目标是把所有（记为p ）个0 放到左边去
设f_i 为前p 个中有i-1 \rightarrow i 个0 的期望操作数- 需要一个前
p 个中的1 和一个后n-p 个中的0 进行交换 - 发现这两个东西的数量都是
p-i+1 - *
f_i=f_{i-1}+\dfrac{n(n-1)}{(p-i+1)^2}
- 需要一个前
- CF1657E Star MST 提交记录
设(u,v) 为点u 和点v 间的边权
先把最小\rightarrow 最大
发现以1 为中心的菊花图是最大生成树
然后发现如果途中存在一个更大的生成树，那么：\ \cdot$ 存在一对 $u,v$，满足 $(1,u)>(1,v) 设
B_i 为满足(1,u)=i 的u 的数量
设f_{i,j} 为确定了B_{i\sim k} ，且\sum_{t=i}^{k}B_t=j 的方案数
答案为f_{1,n-1}
考虑转移，当B_i=k 时：- 这
k 条边可以从剩余的n-1-j+k 条中选择 - 选到的
k 个点间的k(k-1) 条边权可以从1\sim i 中选择 - 选到的
k 个点和已选的点间的k(j-k) 条边权可以从1\sim i 中选择
- 这
- CF660E Different Subsets For All Tuples 提交记录
考虑每一个子序列对于答案的贡献
假设我们选了k 个，分别是a_1,a_2,...a_n
那么为了保证唯一，1\sim a_1-1 不能选a_1 ，a_1+1~a_2-1 不能选a_2 ，……以此类推；a_n+1\sim n 可以随便选
设一下a_n=n-j ，那么方案就是：\sum_{k=1}^{n}\sum_{j=0}^{n-k}C_{n-j-1}^{k-1}\cdot (m-1)^{n-j-k} \cdot m^j\cdot m^k 再设
s=j+k ，那么带入得到：\ \ \ \ \sum_{s=1}^{n}\sum_{j=0}^{s-1}C_{n-j-1}^{s-j-1}\cdot (m-1)^{n-s} \cdot m^s =\sum_{s=1}^{n} (m-1)^{n-s} \cdot m^s\cdot (\sum_{j=0}^{s-1}C_{n-j-1}^{s-j-1}) =\sum_{s=1}^{n} (m-1)^{n-s} \cdot m^s\cdot (\sum_{j=0}^{s-1}C_{n-s+j}^{j}) =\sum_{s=1}^{n} (m-1)^{n-s} \cdot m^s\cdot C_{n}^{s-1} 这个式子可以算
- CF785D Anton and School - 2 提交记录
刚开始推出的答案式子很显然（枚举最右边的左括号）
然后上 范德蒙德卷积公式，就做完了
- CF1540B Tree Array 提交记录
暴力判断每个点为第一个标记（作为根）的答案，最后÷n
预处理左栈有i 个元素，右栈有j 个元素时左边先弹出完的概率
即f_{i,j}=\dfrac{f_{i-1,j}+f_{i,j-1}}{2}
对于一对x,y(x>y) 先找LCA，然后i\rightarrow deep_{lca}-deep_{x} ，j\rightarrow deep_{lca}-deep_{y} 带进去计算即可
- CF1716F Bags with Balls 提交记录
暴力推式子，参考第一篇题解的第二种做法
原式：枚举奇数个数
第 1 步：套公式
第 2 步：移项，拆组合数，约分
第 3 步：把前后两个分数乘起来
第 4 步：把第 3 步乘得的数拆成组合数和提出去的式子
第 5 步：t\leftarrow n-i
第 6 步：把x^{n-t} 拆开
答案：提x^j ，二项式定理
- CF1437F Emotional Fishermen 提交记录
设mx_i=p 的意思是p 为最大的满足2a_p\leq a_i 的非负整数那么 $f_i$ 可以由 $f_{0\sim mx_i}$ 转移 具体的转移： - 多出的鱼排列：$(mx_i-mx_j-1)! - 与之前的方案组合：
C_{mx_i-mx_j-1}^{n-mx_j-2}
- 与之前的方案组合：
- CF1657F Words on Tree 提交记录
每个限制只有正反两种状态
每个点加了限制后只有 一种/两种/无解 的状态
也就是说可以用 2-SAT 解决
但是 2-SAT 真的很难调
- CF1626F A Random Code Problem 提交记录
由于答案乘上n^k 所以期望是个幌子
设f_{i,j} 表示做完前i 次操作后生成的n^i 个序列中，有多少个元素值为j - 这次操作没有选中这
f_{i-1,j} 个元素，f_{i,j}\leftarrow (n-f_{i-1,j})\times f_{i-1,j} [1] - 接下来考虑这次操作选中了这
f_{i-1,j} 个元素： -
-
- 对于任意的
j 都有转移 [1] - 如果
j 不是i 的倍数，有转移 [2][3]，不被转移 [3] 转移 - 如果
j 是i 的倍数，有转移 [2][3]，被转移 [3] 转移 - 转移 [2] 多减的
f_{i-1}{j} 会在自己对自己的转移中补回来
- 这次操作没有选中这