【习题选讲】简单计数题选做（1）

容斥、$dp$ 什么的都是基础，我这块不扎实= = 不能就这么心甘情愿被区分了啊，总是要挣扎的对吧。

LG6075

---

来做绿题了（。发现每个元素是独立的，那算一个的贡献然后 $n$ 次方就好了。发现一个元素取与不取的情况是左下角引一条向右或向上的折线，一直走直到到达边界，这样折线的方案数是 $2^k$，所以总方案就是 $(2^k)^n$。

[USACO20JAN]-Cave Paintings P

---

发现填了一个就要填一块，想到并查集。我们从下往上合并，注意不连通块合并的时候，方案数是相乘的。

[HNOI2015]-落忆枫音

---

$DAG$ 的树形图个数是 $\prod in[i]$（感性理解就是每个点找一个$fa$，由于不会形成环，怎么找都是合理的，据说可以用矩阵树定理证但蒟蒻不会）用严谨的语言表达，这个定理是有向无环图的生成外向树个数为所有入度非 0 的点的入度乘积

再考虑有环的情况，显然要减去一些有环存在的状态（这环一定包含新加进来的那条边啦） 即 $\frac{\prod in[i]}{\prod\limits_{i on circle} in[i]}$。$dp$, $g[x]$ 表示从 $ed$ 到 $x$ 的上面这个东西之和，所以 $g[x] = \frac{1}{in[x]}\sum\limits_y g[y]$。计算 $g$ 数组可以建反图 + 记忆化搜索（注意这里正反的智慧）所以答案就是 $(\prod in[i]) - g[st]$