CF1938M
计数以下序列 \(\lang a\rang\) 的个数：
\[\sum_{i=1}^m a_i=n\\ \forall 1<i<m,(a_i-a_{i-1})(a_i-a_{i+1})>0 \]给出 \(n(n\le 3\times 10^5)\)。
这里的形式大约是 $a_1<a_2{\color{red} >}a_3<a_4{\color{red} >}a_5<a_6\dots $，我们把红色部分拿来容斥。这里把 \(\color{red}>\) 换成 \(\le\) 或者无限制，一个 \(\le\) 就是容斥系数 \(-1\)。
怎么对这样的东西展开计数？我依据“无限制”分开新的序列，把 \(a_1<a_2\le a_3<a_4 ?a_5<a_6\le a_7\dots\) 这里的 \(a_{1:4}\) 和后面的分开。我只需要对一个 \(a_1<a_2\le a_3<a_4\) 型序列计算生成函数后做 SEQ 即可。
这样的序列计算是不难的：只需计算乘积：
\[(1+x-x^2+x^3-x^4+\dots )\times (1+x^2-x^4+x^6-x^8+\dots)\times \dots \]化出来就是
\[\frac{\prod (2+x^i)}{\prod(1+x^i)} \]这是 q-二项式定理及其 \(O(n\sqrt n)\) DP 可以解决的问题。
标签：dots,6.19,le,CF1938M,闲话,times,序列,prod From： https://www.cnblogs.com/british-union/p/18258276/xainhua619