T1

三维BFS乱搞一下应该就可以了吧

T2

经典套路，不难发现每个数最后到达的位置都是固定的

而根据冒泡排序的观点，其实排序也就等价于交换两个相邻的偏序点

$O(n^2)$ 枚举交换即可

T3

GF?

假设我们固定某些位后，其实转换题意后，就是求
$$
\begin{eqnarray}&& \left(\frac{1-x^{m+1}}{1-x} \right)^{L} \
&=& \left(1-x^{m+1} \right)^{L} \left(1-x\right)^{-L}\end{eqnarray}
$$
分别分解得到
$$
\begin{eqnarray}&& \left(1-x^{m+1} \right)^{L}\
&=& \sum_{i=0}^{L}C_{L}^{i}(-x^{im+i})\
&=& \sum_{i=0}^{L}C_{L}^{i}(-1)^{im+i}x^{im+i}\
\end{eqnarray}
$$

$$
\begin{eqnarray}&& \left(1-x\right)^{-L}\
&=& \sum_{i=0}^{+\infty}C_{-L}^{i}(x)^i(-1)^i\
&=& \sum_{i=0}^{+\infty}\frac{(-L)(-L-1)…(-L-i+1)}{i!}(x)^i(-1)^i\
&=& \sum_{i=0}^{+\infty}\frac{(L)(L+1)…(L+i-1)}{i!}(-1)^{i}(x)^i(-1)^i\
&=& \sum_{i=0}^{+\infty}C_{L+i-1}^{i}(x)^i\
\end{eqnarray}
$$

所以就有
$$
\begin{eqnarray}\left(\frac{1-x^{m+1}}{1-x} \right)^{L} &=& \sum_{i=0}^{L}C_{L}^{i}(-x^{im+i})\sum_{j=0}^{+\infty}C_{L+j-1}^{L-1}(x)^j\
&=& \sum_{i=0}^{L}\sum_{j=0}^{+\infty}C_{L}^{i}C_{L+j-1}^{L-1}(-1)^{im+i}(x)^{im+i+j}\
\end{eqnarray}
$$
假设我们要求其第 $d$ 项的值

那么其实就是
$$
\begin{eqnarray}&& \sum_{i=0}^{L}C_{L}^{i}C_{L+(d-im-i)-1}^{L-1}(-1)^{im+i}(x)^{d}\
\end{eqnarray}\

$$
不妨设 $f(x)=\sum_{i=0}^{L}C_{L}^{i}C_{L+(x-im-i)-1}^{L-1}(-1)^{im+i}$

我们要求的就是
$$
\begin{eqnarray}\sum_{d=0}^{P}f(d) &=& \sum_{d=0}^{P}\sum_{i=0}^{L}C_{L}^{i}C_{L+(d-im-i)-1}^{L-1}(-1)^{im+i}\
&=& \sum_{i=0}^{L}C_{L}^{i}(-1)^{im+i}\sum_{d=0}^{P}C_{L+d-1-i(m+1)}^{L-1}\
\end{eqnarray}
$$
这是…组合数前缀和？
$$
\begin{eqnarray}&& \sum_{i=0}^{L}C_{L}^{i}(-1)^{im+i}\sum_{d=0}^{P}C_{L+d-1-i(m+1)}^{L-1}\
&=& \sum_{i=0}^{L}C_{L}^{i}(-1)^{im+i}\left( C_{L+P-i(m+1)}^{L}-C_{L-1-i(m+1)}^{L} \right)\
\end{eqnarray}
$$