\(N,M\le 1e7\)
接着反射容斥，考虑这道题怎么做
如果去枚举不动步数，加上反射容斥，直接T飞了
把-1/0/1操作转换一下，就成了0/1/2
如果没有限制（不能<0或>m），n步方案就是\((1+x+x^2)^n\)
设\(H=1+x+x^2\quad F=H^n\)
那么对两边求导：
\[nH^{n-1}H'=F' \]\[F'H=nFH' \]我们知道
\[H=1+x+x^2,H'=1+2x \]\[[x^i]F'=[x^{i+1}]F*(i+1) \]所以：
\[ \begin{aligned} [x^i](F'H) &= [x^i]F'+[x^{i-1}]F'+[x^{i-2}]F' \\ &=(i+1)[x^{i+1}]F+i[x^i]F+(i-1)[x^{i-1}]F \end{aligned} \]\[ \begin{aligned} n[x^i]FH'=n[x^i]F+2n[x^{i-1}]F &= (i+1)[x^{i+1}]F+i[x^i]F+(i-1)[x^{i-1}]F\\ [x^{i+1}]F&=\frac{(n-i)[x^i]F+(2n-i+1)[x^{i-1}]F}{i+1}\\ &=\frac{n+1}{i+1}([x^i]F+2[x^{i-1}]F)-[x^i]F-[x^{i-1}]F \end{aligned} \]就可以直接递推得出系数了
反射容斥已经说过了
时间复杂度: \(O(n)\)
标签：begin,counting,frac,题解,容斥,aligned From： https://www.cnblogs.com/Linnyx/p/17738189.html