开始还以为是原题大战,后来发现题号是连着的,应该是考完后传上去的.
$common$
考虑分块,将编号 $1\sim n$ 分成 $\sqrt n$ 个块.
做一遍 $dfs$ ,预处理出每个点的 $dfs$ 序,以及它对每一块的贡献次数.
询问时,整块的部分直接调用答案,边角部分利用 $dfs$ 序逐个查询.
时间复杂度 $O(n\sqrt n \log n)$ .
$\text{long long}$ 会被卡,要用 $\text{unsigned long long}$ .
$art$
考虑矩阵树定理,将那 $n$ 个点标号为 $1\sim n$ ,另外 $m$ 个点标号为 $n+1\sim n+m$ .
由于图是一张完全二分图,所以可以直接写出它的基尔霍夫矩阵去掉最后一行一列得到的余子式.
$$
\begin{vmatrix}
m & 0 &\cdots & 0 & -1 & -1 &\cdots & -1 \\
0 & m &\cdots & 0 & -1 & -1 &\cdots & -1 \\
\vdots & \vdots & \ddots & \vdots& \vdots& \vdots& \vdots& \vdots\\
0 & 0 &\cdots & m & -1 & -1 &\cdots & -1 \\
-1 & -1 &\dots & -1 & n & 0 & \dots & 0 \\
-1 & -1 &\dots & -1 & 0 & n &\dots & 0 \\
\vdots & \vdots & \vdots & \vdots& \vdots& \vdots& \ddots& \vdots\\
-1 & -1 &\dots & -1 & 0 & 0 &\dots & n
\end{vmatrix}
$$
这个矩阵的行列式就是答案,比较明显的,可以将它分成 $4$ 个区域,左下角和右上角全都是 $-1$ .
左上角是一个 $n\times n$ 的对角矩阵,对角线上元素都是 $m$ .
右下角是一个 $(m-1)\times (m-1)$ 的对角矩阵,对角线上元素都是 $n$ .
由于这个矩阵十分特殊,我们直接尝试手算它的行列式.
由于前 $n$ 行已经完成了上三角化,只需要对后 $m-1$ 行上三角化.
将前 $n$ 行每一行都乘一个 $\frac 1 m $ ,加到后 $m-1$ 行的每一行中,行列式不变,矩阵被消成了这样:
$$
\begin{vmatrix}
m & 0 &\cdots & 0 & -1 & -1 &\cdots & -1 \\
0 & m &\cdots & 0 & -1 & -1 &\cdots & -1 \\
\vdots & \vdots & \ddots & \vdots& \vdots& \vdots& \vdots& \vdots\\
0 & 0 &\cdots & m & -1 & -1 &\cdots & -1 \\
0 & 0 &\dots & 0 & \frac{n(m-1)}m & \frac{-n}m & \dots & \frac{-n}m \\
0 & 0 &\dots & 0 & \frac{-n}m & \frac{n(m-1)}m &\dots & \frac{-n}m \\
\vdots & \vdots & \vdots & \vdots& \vdots& \vdots& \ddots& \vdots\\
0 & 0 &\dots & 0 & \frac{-n}m & \frac{-n}m &\dots & \frac{n(m-1)}m
\end{vmatrix}
$$
此时,因为下面 $m-1$ 行的前 $n$ 列都是 $0$ ,无论怎样进行行变换都不会变,所以这个矩阵的行列式其实就等于左上角的 $n\times n$ 的矩阵的行列式与右下角 $(m-1)\times (m-1)$ 的矩阵行列式之积.
左上角的那个对角线矩阵行列式显然是 $m^n$ .
对于右下角那个矩阵,我们将每个元素都乘上 $\frac m n$ ,行列式会变为原来的 $(\frac m n)^{m-1}$ 倍,最后答案要乘上系数 $(\frac n m)^{m-1}$ .
右下角的元素乘上 $\frac m n$ 后,得到的新的 $(m-1) \times (m-1)$ 的矩阵是这样的:
$$
\begin{vmatrix}
m-1 & -1 &\cdots &-1 \\
-1 & m-1 &\cdots &-1\\
\vdots & \vdots &\ddots &\vdots\\
-1 & -1 & -1 & m-1
\end{vmatrix}
$$
即主对角线上的元素都是 $m-1$ ,其余元素都是 $-1$ .
如果我们再给他在外面补上一行一列,补成一个 $m\times m$ 的矩阵,
$$
\begin{vmatrix}
m-1 & -1 &-1 &\cdots &-1 &-1 \\
-1 & m-1 &-1 &\cdots &-1 &-1\\
-1 & -1 &m-1 &\cdots &-1 &-1\\
\vdots&\vdots & \vdots &\vdots &\ddots&\vdots\\
-1 &-1 & -1 & \cdots & -1& m-1
\end{vmatrix}
$$
这个 $m\times m$ 的矩阵其实就是一张完全图 $K_m$ 的基尔霍夫矩阵,每个点度数为 $m-1$ ,每两个点之间都有边.
根据矩阵树定理,那个 $(m-1)\times (m-1)$ 的矩阵的行列式就等于完全图 $K_m$ 的生成树个数.
根据 $Cayley$ 定理,或利用 $prufer$ 序列,这个数目应该是 $m^{m-2}$ .
将两个行列式与那个系数 $(\frac n m)^{m-1}$ 乘在一起,就得到了答案.
$$
\begin{aligned}
ans&=m^n\cdot n^{m-1} \cdot m^{1-m} \cdot m^{m-2} \\
&=m^{n-1}\cdot n^{m-1}
\end{aligned}
$$
$hands$
把两种移动方式看做两个向量 $\vec a,\vec b$ .因为题目保证它们不共线,所以每个点都可以被写成 $x\cdot \vec a+y\cdot \vec b$ .
以解出来的 $(x,y)$ 代替原来的坐标,就变成了每次可以向右或向上走一步,可以直接舍去坐标转换后不是整点的点.
要求不能经过障碍点,求起点到终点的方案数.
如果没有障碍,答案显然是 $C_{x+y}^x$ .但现在有障碍.直接递推显然不行,因为新坐标的大小可以达到 $2\times 500^2$ .
将障碍点,目标点视为关键点,记原点为第 $0$ 个关键点.
坐标转换后,按照 $x$ 为第一关键字, $y$ 为第二关键字排序,就做出了一个拓扑序,再进行 $dp$ .
设 $f(i)$ 表示从原点到达第 $i$ 个关键点而不经过其他关键点的方案数.
$g(i,j)$ 表示从第 $i$ 个关键点到第 $j$ 个关键点的所有方案数.
转移有 $f(i)=g(0,i)-\sum_{j=1}^{i-1} g(j,i)\cdot f(j)$ .而 $g$ 不需要考虑障碍,若能够到达,就是组合数,否则是 $0$ .
时间复杂度 $O(n^2)$ .