本文主要是介绍【学习笔记】[ARC156E] Non-Adjacent Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先，记 S = ∑ X i S=\sum X_i S=∑Xi，那么恰好有 S 2 \frac{S}{2} 2S条边（ S S S为偶数）；序列 { X i } \{X_i\} {Xi}合法的充要条件是：
- 对于任意 i i i，满足 X i + X i + 1 ≤ S 2 X_i+X_{i+1}\le \frac{S}{2} Xi+Xi+1≤2S
这种东西 Kidulthood 就很会猜，而我就没有这么好的直觉了😅
然后考虑容斥 X i + X i + 1 > S 2 X_i+X_{i+1}>\frac{S}{2} Xi+Xi+1>2S的位置，显然这构成了一个连续段，并且不超过 2 2 2个。
考虑每一段的生成函数是什么。
1.1 1.1 1.1 总方案数
每一段的生成函数是 1 − x m + 1 1 − x \frac{1-x^{m+1}}{1-x} 1−x1−xm+1，因此 G F GF GF为：
( 1 − x m + 1 ) n ( ∑ ( i + n − 1 n − 1 ) x i ) (1-x^{m+1})^{n}(\sum \binom{i+n-1}{n-1}x^i) (1−xm+1)n(∑(n−1i+n−1)xi)
枚举前面那一项，后面用前缀和算即可。注意算的是偶次方项的系数，复杂度 O ( n m ) O(nm) O(nm)。
1.2 1.2 1.2 只有一个位置不合法
考虑容斥的 i , i + 1 i,i+1 i,i+1构成一段，则枚举 S S S后的 G F GF GF为：
( ∑ S 2 < i ≤ 2 m ( min ( m , i ) − max ( i − m , 0 ) + 1 ) x i ) ( 1 − x m + 1 ) n − 2 ( ∑ ( i + n − 3 n − 3 ) x i ) (\sum_{\frac{S}{2}<i\le 2m}(\min(m,i)-\max(i-m,0)+1)x^i)(1-x^{m+1})^{n-2}(\sum \binom{i+n-3}{n-3}x^i) (2S<i≤2m∑(min(m,i)−max(i−m,0)+1)xi)(1−xm+1)n−2(∑(n−3i+n−3)xi)
枚举第一项即可，其中第二项的取值只有常数个， i i i的下界可以通过第三项取范围消去。复杂度 O ( m ) O(m) O(m)。
1.3 1.3 1.3 有两个位置不合法
枚举中间的数和两边中较小的数之和，以及两边中较大的数的值，然后直接算。复杂度 O ( m 2 ) O(m^2) O(m2)。
总复杂度 O ( n m ) O(nm) O(nm)。
remark \text{remark} remark 看似要枚举的东西很多，但是借助 G F GF GF可以发现实际上要枚举的东西很少。
这篇关于【学习笔记】[ARC156E] Non-Adjacent Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
