题解：P17870 [FJCPC 2026] 变幻自在
Dwl20121022
·
·
题解
思路
定义每个顶点度数均为偶数的简单无向图为偶图，每个顶点度数均为奇数的简单无向图为奇图。
注：定义只是为了好叙述，偶图与奇图有专门的定义。
则偶图与奇图均为好图。
偶图的计算
对一个带标号简单无向图 G，其标号从 1 到 n - 1，则一定存在唯一的 n 与 G 的连线方式，使得所构成的新图为偶图。
:::info[简单证明]
:::
因此偶图个数为 $G$ 的可能情况总数。
$G$ 最多有 $\frac{(n - 1)(n - 2)}{2}$ 条边，每条边可选可不选，共 $2 ^ {\frac{(n - 1)(n - 2)}{2}}$ 种。
## 奇图的计算
与偶图的计算类似，这里给出另一种思路。
由握手定理，图的总度数为边数的两倍，是偶数。
若 $n$ 为奇数，则总度数为奇数，矛盾，因此奇图数为 0。
若 $n$ 为偶数，猜测偶图数与奇图数相等。
只需建立偶图与奇图的一种一一对应关系。
注意到任意一个偶图的所有边取反后即为奇图，且易知不同的偶图取反后得到的奇图互不相同。因为任意一个节点与其他节点的总边数为 $n - 1$，是奇数，取反前一个节点的度数为偶数，则取反后度数为总边数减原度数，是一个奇数，证毕。
结论： $n$ 为偶数时，奇图数等于偶图数。
:::success[Code]
```cpp
#include <cstdio>
using namespace std;
#define ll long long
inline ll fp(ll a, ll b, ll p) {
ll res = 1;
a %= p;
while (b) {
if (b & 1) {
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
inline void solve() {
ll n, m;
scanf("%lld%lld", &n, &m);
if (m == 1) {
printf("0\n");
return;
}
ll k, t1 = n - 1, t2 = n - 2, s;
if (t1 % 2 == 0) s = (t1 / 2) * t2;
else s = t1 * (t2 / 2);
if (n % 2) k = s;
else k = s + 1;
ll ans = fp(2, k, m);
printf("%lld\n", ans);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
```
:::