1001
如果不考虑附魔，我们建立一个 $n \times n$ 的矩阵，其中 $a_{ij}$ 表示一步从 $i$ 到 $j$ 的概率（度数的逆元）。求出这个矩阵的 $k$ 次方为矩阵 $b$， $b_{1n}$ 即为答案。
若考虑附魔，我们将每个点拆成两个点：有附魔的和没附魔的。
对于每座普通桥，分别在有附魔的两个点和没附魔的两个点间连边。对于每座附魔桥，分别在对应的一个有附魔一个没附魔的点间连边。
最后用上文方法求出 $1$ 号普通点和 $n$ 号附魔点之间的概率即可。
单组数据时间复杂度 $O(n^3\log t)$。
1002
枚举含有 $0$ 的列可得
$q_n = \sum\limits_{k=0}^n \binom nk (2c)^k \binom{2n-k}{n-k}$
观察得到
$q_n = [x^n] (1+2cx)^n (1-x)^{-n-1}$
考虑逆用另类拉格朗日反演，则
$\begin{aligned}
[x^n] Q(x) = [x^n] (1+2cx)^n (1-x)^{-n-1} \
= [x^n] \frac1{1+2cx} \left(\frac{x}{x\frac{1-x}{1+2cx}}\right)^{n+1} \
= [x^n] \frac{1+2cx}{1-2x-2cx^2} \cdot \frac{1-2x-2cx^2}{(1+2cx)^2} \cdot \left(\frac{x}{x\frac{1-x}{1+2cx}}\right)^{n+1}
\end{aligned}$
因此，令 $G = x\frac{1-x}{1+2cx}$，$F$ 为 $G$ 的复合逆，则 $Q = \frac{1+2cF}{1-2F-2cF^2}$。
由 $G(F)=x$ 即 $F^2+(2cx-1)F+x=0$ 可以解出
$F = \frac{ 1 - 2 c x - \sqrt{1 - 4 (1 + c) x + 4 c^2 x^2} }2$
代入可得
$Q = (4c^2x^2-4(c+1)x+1)^{-1/2}$
令 $u = 4c^2x^2-4(c+1)x+1$，则
$2Q’u = - Q u’$
可以 $O(n)$ 递推 $Q$ 的系数。
单组数据时间复杂度 $O(n)$。
1003
考虑 DP，$f[i][j]$ 表示前 $i$ 个操作后，坏的电脑在 $j$ 的最小代价。
假设第 $i$ 次交换为 $u_i,v_i$，则 $f[i][u_i]=min(f[i-1][v_i],f[i-1][u_i]+1)$，$f[i][v_i]=min(f[i-1][u_i],f[i-1][v_i]+1)$。
对于其他的位置，$f$ 不变。
则利用滚动数组滚掉第一维，DP 转移每次只用修改 $O(1)$ 个位置的 $f$。
单组数据时间复杂度 $O(m)$。
1004
因为 $a\bmod c=b\bmod c$，所以一定有 $a-b$ 为 $c$ 的倍数，于是枚举 $a-b$ 的因数进行检查即可。
注意特判 $a=b$ 的情况，此时如果 $a=1$，则答案为 $-1$，否则答案为 $2,a$。
单组数据时间复杂度 $O(\sqrt{\max(a,b)})$。
1005
稍加推导后可得出一个结论：
当 $1 \lt +1 \lt y$ 时，$a_i=a_{i+1}+\dfrac{1}{n-i}$。
一波处理可以把原问题等价成一个满足 $x\le y$ 且 $y \times 2 \lt n$ 的问题。
设 $S=\sum\limits_{i=1}^{n-y}a_i$，
由前面的结论可以得到所有 $a$ 与 $a_{y-1}$ 之间的关系，并用 $a_{y-1}$ 表示出 $S$，
容易得到 $a_{y-1}=\dfrac{\sum\limits_{i=y}^{n}a_i}{n-y+1}+1=\dfrac{S}{n-y+1}+1$，
$S=(n-y+1)(a_{y-1}-1)$，
结合之前用 $a_{y-1}$ 表示出的 $S$，就有了 $2$ 条方程，代入 $S=(n-y+1)(a_{y-1}-1)$ 后变为一元一次方程，一波操作后解得：
$a_{y-1}=n-y+1+\sum\limits_{i=y}^{n-1}\sum\limits_{j=1}^i\dfrac{1}{j}-(n-y)\times\sum\limits_{i=1}^{n-y+1}\dfrac{1}{i}$
通过 $a_{y-1}$ 可求得：
$a_x=n-y+1+\sum\limits_{i=y}^{n-1}\sum\limits_{j=1}^i\dfrac{1}{j}-(n-y+1)\times\sum\limits_{i=1}^{n-y+1}\frac{1}{i}+\sum\limits_{i=1}^{n-x}\frac{1}{i}$
在 $O(n)$ 预处理后每次询问可以做到 $O(1)$，总时间复杂度为 $O(n+T)$。
1006
我们考虑维护最左边两个 $0$ 的位置，设其依次为 $a,b$。
若查询时，将 $a$ 设为了 $1$，则答案为 $b$，否则答案为 $a$。
修改时，若修改了 $a$，则令 $a=b$，之后 $b$ 一直递增，直到找到下一个 $0$。
若修改了 $b$，则 $b$ 之后一直递增，直到找到下一个 $0$。
这样整个序列最多被扫过 $2$ 次，总复杂度为 $O(n)$。
1007
首先不难想到对每个 $m$，考虑将 $s$ 个儿子各自安排给 $m$ 个根的方案数；再考虑将剩下的 $n-m$ 个点组合成 $s$ 棵有根树的森林的方案数。
先考虑内层，由经典的 Prufer 序列立刻可知方案数就是
$\binom{n-m-1}{s-1} (n-m)^{n-m-s}$
再考虑外层。显然这就是
$\left[\frac{x^s}{s!}\right] \left(\sum\limits_{i=0}^k \frac{x^i}{i!} \right)^m$
设
$F = \sum\limits_{i=1}^k \frac{x^i}{i!}$
则我们需要计算
$[x^s] \frac1{1-u(1+F)}$
设 $G = F^{<-1>}$ 即 $F$ 的复合逆，根据拉格朗日反演可得答案为
$\frac1s [x^{s-1}] \frac{u}{(1-u(1+x))^2} \left(\frac xG\right)^s$
若计算出 $G$，则容易从中提取所有 $u^m$ 的系数。
接下来叙述如何求出 $G$。
考虑 $F$ 显然满足 ODE
$F = F’ + \frac{x^k}{k!} - 1$
代入 $x = G$ 得
$x = \frac1{G’} + \frac{G^k}{k!} - 1$
整理得
$G’ = \frac{k!}{k(1+x)-G^k}$
解如此的一阶 ODE 可以使用牛顿迭代做到 $O(n \log n)$。
也可以转化为半在线卷积，做到 $O(n \log^2 n)$ 或 $O\left(\frac{n \log^2 n}{\log \log n}\right)$。
1008
直接按题意模拟，每次都会死一个人，所以一定停机。
单组数据时间复杂度 $O(Tn^2)$。