问题1
题意:
给定\(n\),求有多少个\(n\)排列,满足相邻两项绝对值大于\(1\)
将位置看作点,对于点\(i,i+1\),将\(|a_i-a_{i+1}|\)看作边
考虑容斥,钦定边集不合法
考虑单个连通块的多项式\(f(x)=x-2x^2+2x^3-2x^4+\cdots=x\frac{1-x}{1+x}\)
对于点数大于等于\(2\)的,有正反两种排列顺序
枚举连通块的个数
\(F(x)=\sum\limits_{i=0}^{\infty} i!f(x)^i\)
对于一种分段的方法,确定每段最小值的顺序,即可唯一得到排列
那么答案为\([x^n]F(x)\)
令\(g(x)=\sum\limits_{i=0}^{\infty} i!x^i\)
注意到\(x^2\frac{dg(x)}{dx}+(x-1)g(x)+1=0\)
将\(g(f(x))=F(x),f(x)=x\frac{1-x}{1+x}\)带进去
\[\begin{aligned} &\frac{dF(x)}{dx}=\frac{1-2x-x^2}{x^2-2x^3+x^4}(\frac{1+x^2}{1+x}F(x)-1)\\ &(x^2-x^3-x^4+x^5)\frac{dF(x)}{dx}=(1-2x-2x^3-x^4)F(x)+x^3+3x^2+x-1 \end{aligned}\]通过该式容易得到线性递推
问题2
题意:
给定\(n\)、\(m\),求有多少个\(n\)排列,满足不存在长度超过\(m\)的相邻两项绝对值等于\(1\)
定义:若区间内相邻两项绝对值等于\(1\),则称其为连续区间
求不存在长度为\(m+1\)的连续区间,钦定有\(x\)个\(m+1\)的连续区间(可以相交),容斥系数为\((-1)^{x}\)
考虑钦定连续区间后,排列的方案数
观察:若两个连续区间有交,则区间并也为连续区间
将有交的连续区间合并
令\(y\)为连续区间的个数(合并后的,这里长度不一定为\(m+1\)),\(z\)为未被任意区间包含的位置个数
方案数为\((-1)^{x}(y+z)!2^y\)
以下区间均指合并后的区间
记\(f(i,j,k)\)表示把前\(i\)个点分成\(j\)个区间和\(k\)个无限制点的容斥系数和,
\(g(i,j,k)\)表示在上述条件下\(i\)作为区间末尾的容斥系数和
答案为
\[\sum\limits_{j=0}^n\sum\limits_{k=0}^n f(n,j,k)\cdot 2^j\cdot k! \]发现\(j\)这一维没啥用
\[\begin{aligned} F(i,k)=\sum\limits_{j=0}^n f(i,j,k)\cdot 2^j\\ G(i,k)=\sum\limits_{j=0}^n g(i,j,k)\cdot 2^j\\ \end{aligned}\] \[\begin{aligned} &G(i,k)=-\sum\limits_{p=i-m}^{i-1}G(p,k)-2\cdot F(i-m-1,k-1)\\ &F(i,k)=G(i,k)+F(i-1,k-1)\\ \end{aligned}\]答案为
\[\sum\limits_{k=0}^n F(n,k)\cdot k! \]