题意
做法
考虑这样一个问题：
给定\(l,r,len,s,t\)（\(l\le s,t\le r\)）
\(x_0=s,x_{len}=t\)
\(l\le x_i\le r\)
\(|x_i-x_{i-1}|=1\)
计算序列\(x_0,x_1,\cdots,x_{len}\)的方案数
定义1：我们称不满足\(l\le x_i\le r\)的位置\(i\)为不合法位置。
定义2：对于\(x_i<l\)的，我们令其字符为‘L’，对于\(x_i>r\)的，我们令其字符为'R'。将不合法位置的字符顺序连接起来，称其为该序列的不合法字符串。
定义3：对于字符串\(s_1,s_2\)，若\(s_1\)是\(s_2\)的子序列，称\(s_1\in_s s_2\)
结论1：考虑\(A=\{L,R,LR,RL,LRL,RLR,\cdots\}\)，对于任意长度不为\(0\)的不合法字符串\(s\)（\(s\)仅包含字符'L'、'R'），均有：
\[\sum_{x\in A,x\in_s s}(-1)^{|x|}=-1 \]证明略
对于不合法字符串存在子序列\(L\)的序列\(\{x_i\}\)，即\(\exists i.x_i=l-1\)
令最小满足\(x_i=l-1\)的\(i\)为\(\mathbf{i}\)，构建序列\(\{y_i\}\)满足
结论2：通过上述构建，满足如下条件的\(\{x_i\}\)与\(\{y_i\}\)构成双射
\[\begin{aligned} \begin{cases} x_0=s,x_{len}=t~~~~ \\ \exists i.x_i=l-1 \\ |x_i-x_{i-1}|=1 \end{cases} \begin{cases} y_0=2(l-1)-s,y_{len}=t\\ |y_i-y_{i-1}|=1 \end{cases} \end{aligned}\]证明：
令最小的\(i\)满足\(y_i=l-1\)的为\(\mathbf{i'}\)，容易证明\(\mathbf{i'}=\mathbf{i}\)，然后可以通过上述构建的逆将\(\{y_i\}\)得到原来的\(\{x_i\}\)。
对于存在子序列\(RL\)的序列，即\(\exists i<j.x_i=r+1,x_j=l-1\)
令最小满足\(x_j=l-1\)且存在\(i<j\)使得\(x_i=r+1\)的\(j\)为\(\mathbf{j}\)，令最小满足小于\(\mathbf{j}\)且\(x_i=r+1\)的\(i\)为\(\mathbf{i}\)，构建序列\(\{y_i\}\)满足
结论3：通过上述构建，满足如下条件的\(\{x_i\}\)与\(\{y_i\}\)构成双射
\[\begin{aligned} \begin{cases} x_0=s,x_{len}=t~~~~ \\ \exists i<j.x_i=r+1,x_j=l-1 \\ |x_i-x_{i-1}|=1 \end{cases} \begin{cases} y_0=2(l-1)-2(r+1)+s,y_{len}=t\\ |y_i-y_{i-1}|=1 \end{cases} \end{aligned}\]证明：
令最小满足\(y_j=l-1\)且存在\(i<j\)使得\(y_i=2(l-1)-(r+1)\)的\(j\)为\(\mathbf{j'}\)，令最小满足小于\(\mathbf{j'}\)且\(y_i=2(l-1)-(r+1)\)的\(i\)为\(\mathbf{i'}\)，容易证明\(\mathbf{i'}=\mathbf{i}\)，\(\mathbf{j'}=\mathbf{j}\)，然后可以通过上述构建的逆将\(\{y_i\}\)得到原来的\(\{x_i\}\)。
推广结论2和结论3得到：
结论4（更强的结论）：
- 对于所有存在子序列\(RLRL...RL\)（\(k\)个\(RL\)）的不合法字符串的序列\(\{x_i\}\)，满足如下条件的\(\{y_i\}\)可以与其构成双射：
- 对于所有存在子序列\(LRLR...LR\)（\(k\)个\(RL\)）的不合法字符串的序列\(\{x_i\}\)，满足如下条件的\(\{y_i\}\)可以与其构成双射：
- 对于所有存在子序列\(RLRL...RLR\)（\(k\)个\(RL\)加上一个\(R\)）的不合法字符串的序列\(\{x_i\}\)，满足如下条件的\(\{y_i\}\)可以与其构成双射：
- 对于所有存在子序列\(LRL...RLRL\)（\(k\)个\(LR\)加上一个\(L\)）的不合法字符串的序列\(\{x_i\}\)，满足如下条件的\(\{y_i\}\)可以与其构成双射：
证明与结论2的证明类似
容易发现，1.2.的形式可以表示成\(y_0=2k(r-l+2)+s\)（\(k\in \mathbb{Z},k\neq 0\)），3.4.的形式可以表示成\(y_0=2k(r-l+2)+2(r+1)-s\)（\(k\in \mathbb{Z}\)）
令\(f(s,t)\)为\(y_0=s,y_{len}=t\)的方案数，
结合结论1和结论4，下面的式子对于每种不合法的方案数恰好计算了\(-1\)次
又\(f(2\cdot 0\cdot (r-l+2)+s,t)\)即为在不考虑\(l\le x_i\le r\)条件的方案数，故答案为
\[\begin{aligned} &\sum\limits_{k\in \mathbb{Z}}f(2k(r-l+2)+s,t)-\sum\limits_{k\in \mathbb{Z}}f(2k(r-l+2)+2(r+1)-s,t)\\ &=\sum\limits_{k\in \mathbb{Z}}{len\choose \frac{len+t-s}{2}+k(r-l+2)}-\sum\limits_{k\in \mathbb{Z}}{len\choose \frac{len+t+s+2(r+1)}{2}+k(r-l+2)}\\ \end{aligned} \]我们知道\(\sum\limits_{k\in \mathbb{Z}}{n\choose t+km}=[x^t](1+x)^n\mod(x^m-1)\)（\(0\le t<m\)）
故答案即为
\[[x^{\frac{len+t-s}{2}\%(r-l+2)}](1+x)^{len}\mod(x^{r-l+2}-1)\\ -[x^{\frac{len+t+s+2(r+1)}{2}\%(r-l+2)}](1+x)^{len}\mod(x^{r-l+2}-1)\]考虑这样一个二维问题（原题很容易转化为这个问题），
\[\begin{aligned} &Ans=\\ &\sum\limits_{len_1+len_2=len}\left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sx,tx,len_1)-\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)-sx,tx,len_1)\right]\\ &\times\left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sy,ty,len_2)-\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)-sy,ty)\right]\\ &=\sum\limits_{len_1+len_2=len}\left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sx,tx,len_1)\right]\times \left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sy,ty,len_2)\right]\\ &+\sum\limits_{len_1+len_2=len}\left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)-sx,tx,len_1)\right]\times \left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)-sy,ty,len_2)\right]\\ &-\sum\limits_{len_1+len_2=len}\left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)-sx,tx,len_1)\right]\times \left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sy,ty,len_2)\right]\\ &-\sum\limits_{len_1+len_2=len}\left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sx,tx,len_1)\right]\times \left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)-sy,ty,len_2)\right]\\ \\ \end{aligned} \]给定\(len,sx,sy,tx,ty\)（\(1\le sx,tx\le n,1\le sy,ty\le n\)）
\(x_0=sx,y_0=sy\)
\(x_{len}=tx,y_{len}=ty\)
\(1\le x_i\le n\)
\(1\le y_i\le n\)
\(|x_i-x_{i-1}|=1\land y_i=y_{i-1}\)或\(x_i=x_{i-1}\land |y_i-y_{i-1}|=1\)
计算序列\((x_0,y_0),(x_1,y_1)\cdots,(x_{len},y_{len})\)的方案数
对于\(\sum\limits_{len_1+len_2=len}f(sx,tx,len_1)\times f(sy,ty,len_2)\)的组合意义为从\((sx,sy)\)走\(len\)步到达\((tx,ty)\)的方案数
考虑进行坐标转换\((x,y)\rightarrow (x+y,x-y)\)，那么每一步的增量变为\((+1,+1)(+1,-1)(-1,+1)(-1,-1)\)
也就是每一步每一维可以单独处理，则：
\(\sum\limits_{len_1+len_2=len}f(sx,tx,len_1)\times f(sy,ty,len_2)=f(sx+sy,tx+ty,len)\times f(sx-sy,tx-ty,len)\)
考虑\(Ans\)的第一项如何计算（\(N=2(n+1)\)），另外三项同理
\[\begin{aligned} &\sum\limits_{len_1+len_2=len}\left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sx,tx,len_1)\right]\times \left[\sum\limits_{k\in \mathbb{Z}}f(2k(n+1)+sy,ty,len_2)\right]\\ &=\sum\limits_{k_1\in \mathbb{Z},k_2\in \in \mathbb{Z}}f(2(k_1+k_2)(n+1)+sx+sy,tx+ty,len)\times f(2(k_1-k_2)(n+1)+sx-sy,len)\\ &=\left[\sum\limits_{k\in \mathbb{Z}}f(2kN+sx+sy,tx+ty,len)\right]\times \left[\sum\limits_{k\in \mathbb{Z}}f(2kN+sx-sy,len)\right]\\ &+\left[\sum\limits_{k\in \mathbb{Z}}f((2k+1)N+sx+sy,tx+ty,len)\right]\times \left[\sum\limits_{k\in \mathbb{Z}}f((2k+1)N+sx-sy,len)\right]\\ &=\left[[x^{?_1}](1+x)^{len}\mod(x^{2N}-1)\right]\times \left[[x^{?_2}](1+x)^{len}\mod(x^{2N}-1)\right]\\ &+\left[[x^{?_3}](1+x)^{len}\mod(x^{2N}-1)\right]\times \left[[x^{?_4}](1+x)^{len}\mod(x^{2N}-1)\right]\\ \end{aligned}\]回到原题，可以在\(O(N\log N\log len)\)倍增求出\((1+x)^{len}\mod(x^{2N}-1)\)，然后每次\(O(1)\)回答询问
标签：mathbb,Square,limits,gym104077I,sum,len,le,Grid,2k From： https://www.cnblogs.com/Grice/p/18328120