The 2021 ICPC Asia Shanghai Regional Programming Contest B. Strange Permutations

题目链接
破防了，上周很套路的ds题调半天还以为只是码力下降了，现在发现原本比较自信的计数能力也不行，不明白为什么连简单的容斥都想不清楚...

把题意抽象一下，就是有一个长度为n的排列对应的有向图，需要依次经过每一个点，并且不经过给定的边。

那么显然考虑容斥，枚举至少经过几条给定的边。然而如果对于序列考虑，这个经过关键边的顺序又要受到环长的限制。原本就觉得每一段长度不同的关键边对应的限制都不同，就以为不可做。

但是只要从选取哪些关键边考虑，就会发现每选一条边，其实就是把一个点合并到另一个点。因为每选取一段连续的关键边，就要求从这一段的开头按照顺序走到结尾，那就是把这一段缩成一个点。所以对于每一个环，直接考虑它选取了多少条关键边，就能确定缩成几个点，直接写成一个[环长]次的多项式,然后分治fft即可。

对于这种有比较具体限制的问题（输入不只是几个数），容斥的时候应该从容斥的对象考虑，思考容斥的那个集合所带来的影响是什么。而不是直接从合法答案的角度，去构造满足对应至少不合法个数的解，这样容易陷入混乱。