回复 @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;

 }

};

所以7的神奇之处是什么呢？提示：完美匹配的一列状态数和回路的一列状态数……
计算那个“一列”的转移用时很少，即使是低效的DFS也能秒出
这道题用n^3矩阵乘是过不了的，优化方法：矩阵稀疏的一笔（这也是DFS秒出的原因）……
这种把三道插头DP简单粗暴加起来的题真是蛋碎……
所以数据比较奇怪（可以看到远小于2^64-1），恰好能卡掉n^3矩阵乘，至于能过的代码，时间和我在uva上的差不多
然后uva的评测机真快……