[Xmas Contest 2024] Artistic Modulus 题解

· · 题解

题目链接

题意

给定一个不超过 2\,024 个点和 2\,024 条边的无向简单图。求出对它的点和边的金银染色方案，满足每条金边旁必有至少一金点，每个银点旁必有至少一银边的方案数，对 \textbf{2} 取模。

多测。最多 100 组数据。

题解

这个形式太不对称了，考虑把边的颜色互换，这样就都是要求银的旁边有至少一个金的了。

因为至少一个不好处理，考虑容斥。因为对 2 取模，容斥系数都是 1。钦定若干条银边/点不合法，我们称之为铜边/点。则就是求三染色方案数，满足铜边旁边都是银点（或铜点，因为铜点是被钦定不合法的银点），铜点旁边都是银边或铜边。

换言之，铜的东西旁边不能是金的，或者说不能有铜金相邻。因此，对于每个方案，把铜和金互换也是一个方案，可以抵消。唯一剩下来的方案是全银，因此答案恒为 1。

代码

#include <bits/stdc++.h>
using namespace std;
int t;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>t;
    while(t--)
    cout<<"1\n";
    return 0;
}

致谢

感谢 @Galois_Field_1048576 在此题上给我的帮助。