P4708 画画 题解

先叠层甲。

此解法非本题正解

如果想看正解可以去看上面 \(Sdchr\) 或 \(Log_x\) 大佬的。

第一眼看到此题，\(N\) 个点的无标号的每个连通块有欧拉回路的图的个数。
这不就是 \(N\) 阶赛德尔矩阵的个数吗？

什么？你不知道赛德尔矩阵是什么。没关系。这东西是个很小众的东西。百度上都基本查不到，只不过我碰巧看到过，然后我们就可以在翻译软件上翻译 \(N\) 阶赛德尔矩阵个数，英文为 \(number\) \(of\) \(Seidel\) \(matrices\) \(of\) \(order\) \(n\) 然后我们在 \(OEIS\) 上查一查。

根据样例检查一下，对的，没问题。

我们将这个数列复制下来，用代码取模。
然后存进一个数组。

Code

#include <bits/stdc++.h>
using namespace std;
int a[51]={1,1,2,3,7,16,54,243,2038,33120,1182004,87723296,907260828,445874017,131059413,750854059,85710140,46269468,106575268,569924828,477980796,853121491,916490672,848722293,179336057,577163661,709912061,916083428,988859367,286999618,29547862,713350279,194424628,553076032,609634772,876525030,182311698,148716617,346128108,650982654,373128192,361260409,524419271,834718796,514750301,478609700,386216865,881562716,715225681,602577017};
int main()
{
	int n;
	cin>>n;
	cout<<a[n-1];
}