题解：P17870 [FJCPC 2026] 变幻自在

wanganze · 2026-11-13 14:46:55 · 题解

题意

求 n 个点的有标号无向图中每个点度数同奇偶的图的个数。

分析

对 n 分奇偶讨论。无向图的所有点度数之和是偶数。

当 n 为奇数时，因为所有点的度数之和必须是偶数，所以显然每个点的度数都是偶数。不妨考虑前 n-1 个点，允许它们任意取或不取，那么想要让所有点的度都是偶数，最后一个点 n 连向前 n-1 个点的边都是唯一确定的。而由于和最后一个点连边之前，前 n-1 个点的度数和是偶数，所以一定有偶数个奇度点，那最后与点 n 连的边也是奇数条。所以答案为 2^{\frac{n(n-1)}2}。

当 n 为偶数时，所有点的度数可能是奇数或偶数。偶数的情况同上，奇数的情况我们可以取偶数情况的补图，那么每个点新的度数 d'=n-1-d 就是奇数，和原图一一配对。因此答案为 2^{\frac{n(n-1)}2+1}。

实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL qmi(LL a,LL k,LL mod)
{
    LL res = 1;
    a %= mod;
    while(k)
    {
        if(k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
int main()
{
    int t;
    cin>>t;
    while(t --)
    {
        LL n,m;
        cin>>n>>m;
        if(n & 1) cout<<qmi(2,(n - 1) / 2 * (n - 2),m)<<'\n';
        else cout<<qmi(2,(n - 2) / 2 * (n - 1) + 1,m)<<'\n';
    }
    return 0;
}