有一个-n�nn-维-nn�n1n−n1nn×nn�n2n−n1nn×n⋯n×nn�n�n−n1nna-n1nn-−1×a-n2nn-−1×⋯×a-nnnn-−1-超立方体。左下角坐标为-nn1nn1nn…nn1nn11…1右上角坐标为-nn�n1nn�n2nn…nn�n�nna-n1nn-a-n2nn-…a-nnnn-。nn考虑一个无向图有-n�n1n×n�n2n×n⋯n×n�n�na-n1nn-×a-n2nn-×⋯×a-nnnn--个有标号的结点。结点的标号分别为-nn�n

题目翻译

给定一个 $n$ 维 $(a_1-1)\times(a_2-1)\times\cdots\times(a_n-1)$ 的超立方体，左下角坐标为 $(1,1,\cdots,1)$，右上角坐标为 $(a_1,a_2,\cdots,a_n)$。定义 $a_1\times a_2\times\cdots\times a_n$ 个结点分别代表超立方体内或边界上的整点。对于两个结点 $(x_1,x_2,\cdots,x_n)$ 和 $(y_1,y_2,\cdots,y_n)$，如果它们对应的超立方体内或边界上的整点构成了一条边，则它们之间有一条无向边。给定一个这样的图，求其生成树个数对 $998244353$ 取模的结果。

题解

考虑树形 DP。设 $f(u,v)$ 表示以 $u$ 为根的生成树个数，其中 $u$ 的父亲节点为 $v$。显然，如果 $u$ 和 $v$ 之间的连边是沿着第 $i$ 维的，则要求 $u_i=v_i+1$ 或 $u_i=v_i-1$。因此，我们可以枚举 $i$，对于每个 $i$ 分别计算出所有满足条件的 $(u,v)$，并进行转移。

具体来说，如果 $v$ 沿着第 $i$ 维的值是 $j$，则枚举 $u_i$ 的值，若 $u_i=j-1$ 或 $u_i=j+1$，则连边 $(u,v)$。转移方程为：

$$f(u,v)=\sum\limits_{(u',v')\in E}f(u',v)\prod\limits_{i=1}^n[x_{u,i}=x_{u',i}]\prod\limits_{i=1}^n[y_{v,i}=y_{v',i}]$$

其中 $E$ 表示所有与 $v$ 相连的点 $u'$。

时间复杂度 $O(na_1a_2\cdots a_n)$，可以通过本题。

代码

（代码中的 $B$ 表示取模的数）