要减肥早晨

文章
3
资源
0
加入时间
2年10月17天

AGC022F - Checkers

题目链接最近做的最神仙的一道DP/计数题。原本的想法是A关于B对称,就新建一个点C,A向这个点连一条-1的边,B连2的边,这样两种方案不同当且仅当存在一个点到根路径的乘积不同,但这样要同时关心2,-1的个数,难以计数。发现乘积只跟-1的奇偶性有关,先考虑2的边,把-1的边缩起来,直接把A放到C上,这样就相当于B连向A,把A取反,于是问题变为计算这样的n个点的有标号的树的个数,两棵树不同当且仅...