luogu 6478
Solution :

问的是i恰好 =0 . ..m的情况数量,涉及排列限制,对于恰好的显然不好做(其实对于每个点都有对应的匹配,但是如果当成匹配计数会非常非常的麻烦)

可以通过二项式反演或者容斥之类的东西直接转化成求至少有i对匹配的方案数,设至少是g,恰好是f,容易知道f(k)=\sum_{i\geq k}^m\binom{i}{k}(-1)^{i-k}g(i)

然后想g怎么算,直接匹配计数复杂度爆炸,随便按个\rm dp上去试试

g_{u,x}表示u子树内匹配了 x对的方案数;最后回到根的时候发现只能算出来匹配了m对的,这个是直接算出来的答案,但是对于i<m的情况算出来的其实是至少,并且是钦点好的至少,对于剩下的还没有钦点,所以g_{1,x}\times(m-x)!,也就是对剩下的点随机匹配之后的总方案数就变成了上面容斥里的的g

\rm dp转移的时候,对于当前的点u,看看他是A/B,然后在子树里找取反的颜色,假设匹配完了剩下res个,就是g_{u,x+1}=g_{u,x}\times res+g_{u,x+1} ,需要带上原来子树里有的。对于子树之间的合并,发现完全不合法,所以只能每个子树内单独选,不能跨子树匹配,那就直接加法卷积背包统计。

算当前点u和子树结合的时候,先合并子树答案然后再用当前点匹配子树中的点比较好算

复杂度O(n^2)

luogu 4965
Solution :

不管怎么样看起来方案都非常难处理(状态乱七八糟),所以考虑先尝试模拟这个信的变化:

一个比较朴素的想法是用\rm trie树表示一下,最浅的那个叶子Mx就是初始的文章状态,如果当前要输入一个字母,那显然这个最浅状态叶子下面的所有节点在没有对应字母儿子的情况下都会长出对应字母的儿子(因为对于每个点都表示了一个文章状态前缀,也就是一种可能的情况,需要对所有可能情况加点),对于Mx节点上面的节点,因为文章在初始是确定的所以不会发生变化;但是如果删除一个字母的话,除了Mx节点以外其他的所有状态实际上都已经出现了,所以不会变化,但是对于Mx来说,他父亲节点的状态还没有出现,所以为了能表示这段,Mx就变成了他的父亲节点。

容易知道节点的总数量实际上就是文章的可能数量,考虑加入一个字母K的时候总节点数怎么变化

对于有K对应儿子的节点不会再长出对应的儿子,所以就是除去Mx上面节点以外的总节点量-所有节点K儿子的量,那只需要对于每个字母记录当前的作为儿子的总量即可。

Mx上面那部分需要特殊处理,如果移动了,那么就对原Mx+1,而不是移动到的点,因为统计的是K作为儿子节点的量而不是父亲节点;同时如果已经到原文章第一个字母了就不需要再移动了。

复杂度O(n+m)

容斥 树上问题 组合计数 dp Trie 模拟

2022.10.11补
上一篇 «
2022.10.8补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors