by fitasch

A[J]

E[G]

面值分别为1 2 3的硬币各a b c枚
问能组成的面值个数

乱搞

先考虑3 3 3 2 2 1 ...这样的方案,共a+b+c
然后若至少有1个1,则可以为所有的 3 和 2 贡献 b+c
若至少有2个1,或者1个2,则可以为所有的 3 贡献 c
若至少有两个2,则又可以为所有的 3 贡献 c-1 (注意与1的贡献重复)
考虑所有的2连到倒数第二个3后面,那么2又可以贡献b-1 (注意与1的贡献重复)

F

H

一棵树,结点$a_i,b_i$间有$2c_i$条路径
求欧拉回路的数量

树形dp

$d[u]$表示从u出发又回到u的方案数
考虑将没两条路径视为一组,然后对于当前$u$
下面的推论需要yy

先考虑从子节点回到u,一共有$\prod c_{u,v}!$ 然后乘上依此插空的个数
考虑父亲从父亲节点回到u,因为要留一条路径回父亲结点,因此是$c_{fa,u}$个空插所有子节点的路径
因为其向上更新的时候已经乘上了阶乘,所有不用乘阶乘…

BEST定理

由于n很大,不能用Matrix-Tree定理计算外向树
不过由于数据特殊,其本身就是一棵树,两个节点间一半为出边,一半为入边
所有欧拉图的外向树的个数为$\prod C_{2c_i}^{c_i}c_i$
即所有边选一半作为出边,然后再选择一条作为树边
然后算出每个点的入度,由BEST定理计算出欧拉回路个数

I

有n(5)个数,给定取值范围分别为$[a_i,b_i]$(1e3),求其中LIS长度为1..n的序列个数

枚举 DP

n!枚举n个数的大小关系,若$rank(i) < rank(j)$
若$i < j$则$t_i < t_j$,否则$t_i \geq t_j$
这样可以不重复地表示所有关系

然后按rank从小到大dp

复杂度$n!nmax(b_i)$

J