PKUCPC2011 F:Hamilton Circles — 矩阵乘法

F:Hamilton Circles

总时间限制: 1000ms 内存限制: 65536kB

描述

Bob has a cuboid of size 2 × 2 × n. Consider every 1 × 1 × 1 grid of the cuboid as a vertex and there is an edge between two vertices if and only if the corresponding grids have a common surface. How many hamilton cycles are in this graph? A hamilton cycle is a cycle which visits each vertex exactly once and returns to the starting vertex at last.

输入

The first line contains an integer T(T < 100) indicating the number of test cases.
In each test case, there is an single line containing an integer n(1 ≤ n ≤ 1000000000). 　

输出

For each test case, print the case number and the number of hamilton cycles in a single line. The answer may be very large, so you should divide this answer by 1000000007 and just output the remainder instead. Please follow the format of the sample output.

样例输入

4
1
2
3
10

样例输出

Case 1: 1
Case 2: 6
Case 3: 22
Case 4: 221542

题目大意：

给定2*2*n的立体网格图，（也可以看成n个1*1*1依次相连的正方体所有顶点构成的图）。我们规定，当且仅当两个点存在于同一个正方体中且相连，这两个点在网格图中才存在一条边。求这样的网格图中不同的哈密顿回路数，答案对1000000007取模。（1 ≤ n ≤ 1000000000）

       注：哈密顿回路是指由某一起点出发并返回该点的路径，途中经过所有其他节点且只经过一次。

题目解析：

       我们可以首先根据哈密顿回路的性质知道，我们只需要满足每个点连接且仅连2条边，并构成通路即可。即变成求不同连边方式满足上述条件。

我们可以继续发现，该图具有较强分层性质，即可以变成层内连接方式和相邻两层之间的连接方式。因此我们可以较为自然的想到利用递推的方式解决问题。

我们可以考虑新加一层点之后的状态转移。也就是我们假定前k层构成了合法的哈密顿回路，新加一层之后，我们需要且仅需要删除第k层部分连边，连向k+1层，并在k+1层内合理连接构成合法方案。这个时候我们发现，如果两层之间的连边确定的话，最后一层的合法连边方案是存在且唯一的。那么也就变成了从第k层删除某些边转移到k+1层统计方案数。

那么我们就考虑最后一层的所有合法状态。共7种，其中第一种当且仅当n=1时成立，其他为n>1时成立。

我们考虑状态转移，可以发现同时删除相邻两条边不合法，其他状态全部合法，即可以得到k+1层的状态。

这样我们可以自然的使用dp进行问题求解。但是，我们发现n的范围非常大，所以需要进行优化。我们发现状态数是非常少的，所以可以使用矩阵乘法加速求解。

最后时间复杂度为O(7³log n)

代码实现：

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 100010
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct qaz{
    ll a[7][7];
    qaz(){
        memset(a,0,sizeof(a));
    }
    qaz operator *(const qaz &b){
        qaz c;
        for(int k=0;k<7;++k)
            for(int i=0;i<7;++i)
                for(int j=0;j<7;++j)
                    (c.a[i][j]+=a[i][k]*b.a[k][j])%=mod;
        return c;
    }
}I,A,ans;
int T,n;
qaz ksm(qaz A,int b){
    qaz ta=I;
    while(b){
        if(b&1) ta=ta*A;
        A=A*A;b>>=1;
    }
    return ta;
}
void INIT(){
    for(int i=0;i<7;++i) I.a[i][i]=1;
    A.a[0][1]=A.a[0][2]=A.a[0][3]=A.a[0][4]=A.a[0][5]=A.a[0][6]=1;
    A.a[1][1]=A.a[1][3]=A.a[1][5]=1;
    A.a[2][2]=A.a[2][4]=A.a[2][6]=1;
    A.a[3][2]=A.a[3][4]=A.a[3][5]=A.a[3][6]=1;
    A.a[4][1]=A.a[4][3]=A.a[4][5]=A.a[4][6]=1;
    A.a[5][2]=A.a[5][3]=A.a[5][4]=A.a[5][6]=1;
    A.a[6][1]=A.a[6][3]=A.a[6][4]=A.a[6][5]=1;
}
ll Ans;
int main(){
    INIT();
    T=rd();
    for(int _=1;_<=T;++_){
        n=rd();
        ans=ksm(A,n-1);
        Ans=0;
        for(int i=0;i<7;++i) Ans+=ans.a[0][i];
        printf("Case %d: %lld\n",_,Ans%mod);
    }
    return 0;
}