题目链接
题意关键词：DAG，k种颜色，求长度为l的同色链的cnt平方
做法关键词：平方拆贡献，卡常，dp，二项式反演，容斥，二项式定理，k-1
好题，绝世好题。先放一张白板图用以辅助理解。左上角写错了是cnt^2.
首先转化题意，容易将平方拆贡献，于是就成了我们要求两条长为l的链组成的有序对(x,y)的方案。
一种选取的方案还要再乘上其自身的颜色方案k与其他未被覆盖的区域的颜色方案\(k^{n-|x\cup y|}\)，转化一下发现x与y的交会影响其计数。
但是强制要求经过p个点难以直接计数，因为那样需要在转移的时候确保相邻两个转移点之间没有相交、
因此，我们选择二项式反演，仅仅钦定若干点，这样转移的时候中间就可以任意行走不考虑是否相交。沿着这个思路，我们设计状态\(f_{u,p,l1,l2}\)表示钦定当前两条链尾都在u汇合，包括前面已经钦定了p个交点，第一条链长l1，第二条链长l2的方案数。
转移过程需要预处理三个东西，\(g_{u,v,x}\)表示从u到v长为x的方案，\(s_{u,x}\)和\(t_{u,x}\)则分别统计以u为末尾/开头，长为x的链的数量。
那么初始状态就是\(f_{u,1,l1,l2}=s_{u,l1}\times s_{u,l2}\)，转移枚举v然后乘相应g即可。复杂度\(O(n^2l^5+n^3l)\)，没法通过。
优化方向有二，其一是去状态，将p用二项式定理优化掉；其二是少转移，将中间对l1,l2的转移进行分步。
先讲第一种，看到白板右下角推导过程，由于钦定的结果偏小，实际情况是多统计了那些有更多交点的方案，因此容斥时减去钦定更多的部分。然后交换枚举顺序并运用二项式定理得到结果。这就意味着，我们大可不必显式记录p，而是每次转移乘一个k-1就行了。
再说第二种，我们试着将f中的l1,l2看做形式变量x,y的幂次，那么\(f_u(x,y)\)就是一个二元多项式。而转移实质也是乘了一个二元多项式\(g_{u,v}(x)\times f_{u,v}(y)\)。我们可以运用结合律，将其作两次乘进去，复杂度就会下降。
做了两个优化后的复杂度是\(O(n^2l^3+n^3l)\)，后者是用来求g的。