题目名称	1528. [UVa 11276] 神奇的七
输入输出	`magicalseven.in/out`
难度等级	★★★★☆
时间限制	2000 ms (2 s)
内存限制	256 MiB
测试数据	7
题目来源	cstdio 于2014-02-20加入
开放分组	全部用户
提交状态
分类标签	动态规划快速幂插头DP 状态压缩矩阵运算稀疏表 UVa
	分享题解

关于神奇的七的近10条评论(全部评论)
回复 @cstdio : 如果像我第一次那样写矩阵乘法，为什么也过不了啊！？这样和vector应该只是常数上的区别吧…… `struct matrix{ int a[N][N]; void clear(){memset(a,0,sizeof a);} void operator = (const matrix &x){ static ll ans[N][N]={0}; for (int i=0;i<N;i++) for (int k=0;k<N;k++) if (a[i][k]) for (int j=0;j<N;j++) ans[i][j]+=a[i][k]x.a[k][j]; for (int i=0;i<N;i++) for (int j=0;j<N;j++) a[i][j]=ans[i][j]%10000,ans[i][j]=0; } };` FoolMike 2017-06-21 19:44 2楼
所以7的神奇之处是什么呢？提示：完美匹配的一列状态数和回路的一列状态数…… 计算那个“一列”的转移用时很少，即使是低效的DFS也能秒出这道题用n^3矩阵乘是过不了的，优化方法：矩阵稀疏的一笔（这也是DFS秒出的原因）…… 这种把三道插头DP简单粗暴加起来的题真是蛋碎…… 所以数据比较奇怪（可以看到远小于2^64-1），恰好能卡掉n^3矩阵乘，至于能过的代码，时间和我在uva上的差不多然后uva的评测机真快…… cstdio 2014-02-20 22:28 1楼

1528. [UVa 11276] 神奇的七

★★★★☆ 输入文件：magicalseven.in 输出文件：magicalseven.out 简单对比
时间限制：2 s 内存限制：256 MiB

7是一个非常神奇的数。它是最小的，不能被表示成少于四个非负整数的平方的数。它也是大于1的最小快乐数。7在许多文化中被认为是有魔力的。在这个问题中，你将发现隐藏在图论中关于7的神奇魔术。

给出一个大小为7*n的网格G，如下所示（图的顶点是所有格子的中心，两个顶点相邻当且仅当它们的格子有一条公共边）。计算出A+B+C的末四位数字，其中

A = G的完美匹配的总数。完美匹配指覆盖了所有顶点的匹配。

B = G的哈密顿圈的个数。一个哈密顿圈访问了所有的顶点恰好一次，并且最终回到开始的顶点。

C = G的生成子图的个数，要求子图的每个连通分量都是一个圈。

输入文件包含不超过30行，每行包含一个正整数，即n的值。这些n的值都不超过64位无符号整数的范围。

对每组数据，输出一行。如果A+B+C不超过四位，在高位用0补齐。否则，按同样的方法输出A+B+C的后四位。

0000

0030

5900

5765

鉴于评测机的具体性能，对UVa上的数据范围进行了相应的变动。

如果你使用了STL，请注意打开O2开关。

Problem setter: Josh Bao Alternative Solution: Mike Liu