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

· · 题解

你考虑增量构造状物，最后加进去一个点可以控制前面所有点的奇偶性，这可太强大了。

然后注意到度数和一定是偶数，所以 n 是奇数的时候点的度数只能是偶数，先做这种情况。你发现把前面所有点的度数改成偶数了以后当前点也一定是偶数，于是前面的就可以任意选了。

接下来是 n 是偶数的情况，如果前面全部都是偶数，因为度数和是偶数所以当前点也是偶数，前面都是奇数的时候同理得到当前点是奇数，于是无论什么情况前 n-1 个点都是可以随意选的。

于是答案就是 2^\binom{n-1}2，如果 n 是偶数还要再翻个倍。快速幂即可。

void solve(){
    int n,m;
    cin>>n>>m;
    cout<<qpow(2,(n-1)*(n-2)/2,m)*(n&1?1:2)%m<<'\n';
}
// 想把话语藏在心头忍住不说出口
// 是否这样最后也会减少一点心痛