省流：没有红太阳我效率很低。没洗头发我效率很低。
[ABC281G] Farthest City
这好像是个智障题。
我们考虑生成最短路树，而最短路树之后还可以连边。我们发现如果一个点向深度相同的点连边，或者是比自己高一层的点连边，是不会影响到自己在最短路树的距离的。
我们不考虑最后一个点，最后将它连在最后一层。所以考虑一层一层地加点，设 \(f_{i,j}\) 表示已经用了 \(i\) 个点，最后一层的点数为 \(j\) 的方案数。然后转移就简单多了
$f_{i,j}=\sum\limits_{k=1}^{i-j} f_{i-j,k}\times \dbinom {n-1-i+j}{j}\times {(2{k}-1)}j\times 2^{\dbinom j 2} $
第一个组合数是从剩下的点选 \(j\) 个，然后是每个点可以向上一层的点随便连边，但不能不连，所以就是 \((2^k-1)^j\)，然后也可以向同层连边，同层连边有 \(\dbinom j 2\) 条，都有连或不连两种。
最后的答案就是 \(\sum \limits_{j=1}^{n-1} f_{n-1,j} \times (2^{j}-1)\)
[ABC281Ex] Alchemy
首先是可以选等级为 \(1\) 的宝石是随便选的。那么每种宝石能选的生成函数就是 \((1+x)\)，\(A\) 种就是 \(F(x)=(1+x)^A=\sum\limits_{i=0}^A \dbinom A i x^i\)
然后等级更高的每种都能选一个。假设等级为 \(2\) 或更高的宝石有 \(a_i\) 个，那么生成函数就是 \((1+a_ix)\)
那么 $a_n=[x^n] F(x) \prod \limits_{i=0}^ {n-1} (1+a_i) x $
假设 $g(i)= [x^i]\prod (1+a_jx) $
那么 $a_n = \sum \limits_{i=0}^n f(i) g(n-i) $
我们发现 \(g\) 需要依赖前面的项才能求出来，所以用分治 NTT 即可。
闲话
我想听歌了
满眼繁星占领我内心，
撑起腐朽夜空。
手点着微芒，想照亮那隐约角落，
转瞬即逝，如烟火抱憾落幕（寞）
将我隐藏，成为星空崭新的孤岛。