#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
struct node
{
    long long a[35][35];
    node()
    {
        memset(a,0,sizeof(a));
    }
};
int he;
long long p;
int s[8]={0,3,6,12,15,24,27,30};
node chengfa(node a,node b)
{
    node c;
    for(int i=0;i<he;i++)
    {
        for(int j=0;j<he;j++)
        {
            for(int k=0;k<he;k++)
            {
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
            }
        }
    }
    return c;
}
int main()
{
    int m;long long n;
    node pre,ans;
    he=1;
    scanf("%lld%d%lld",&n,&m,&p);
    for(int i=1;i<=m;i++)he*=2;
    for(int i=0;i<he;i++)ans.a[i][i]=1;
    for(int i=0;i<he;i++)
    {
        for(int j=0;j<he;j++)
        {
            if(((~i)&j)==((~i)&(he-1)))
            {
                int bk=0;
                for(int k=0;k<8;k++)
                {
                    if((i&j)==s[k])bk=bk||(i&j)==s[k];
                }
                pre.a[i][j]=bk;
            }
        }
    }
    long long x=n;
    while(x>0)
    {
        if(x%2==1)ans=chengfa(pre,ans);
        pre=chengfa(pre,pre);
        x/=2;
    }
    printf("%lld\n",ans.a[he-1][he-1]);
    return 0;
}

http://blog.csdn.net/lixuanjing2016/article/details/77603392

matrix67 太神了！！

VJ复活后的第一题 纪念下

郁闷 这个也可以标难度1？？伤人自尊那

借用了大牛们的方法，我才得以很快地解决，不过我也非常害怕，

方法会很快忘记啊！！！

好伤心啊。。。

自己预处理，自己状态压缩，自己递推 了 1小时

结果一看生成出来的答案发现要用矩阵乘法。。

我不会啊。。。。

白弄了。。。。。

杯具。。。

很强大的矩阵乘法题………………

方法楼下很多大牛都讲过了

矩阵范围是

0~2^m-1 打成 1~2^m-1 ，结果就错了

大家要注意啊

有点难啊

伤自尊

看matrix67神牛的代码AC了

用了一天半，才看懂了大牛们的代码和题解。提交了4次，结果是因为 位运算的优先级.....实在是太笨了！！

谢谢各位大牛啊！！

把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。

-from：http://www.matrix67.com/blog/archives/276

可以用加法原理解释

1.因为每个格子不是被覆盖就是没被覆盖，状态只有0 1两种，m0)do

Begin

If(N And 1>0)Then

F:=Times(F,G);

G:=Times(G,G);

N:=N Shr 1;

End;

Writeln(F[Max,Max] Mod P);

End.

lhc...JYY(超级大委男)...

居然AC的第100题是这个...无语...

orz...

看了matrix67的题解，一遍AC（今天已经靠matrix67一遍AC了3题……）

题解见此：

http://www.matrix67.com/blog/archives/276

原来是 De Bruijn

。。。。

又是 矩阵乘法 快速幂

不懂的 去看 matrix67 神牛的blog

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 0ms

├ 测试数据 23：答案正确... 0ms

├ 测试数据 24：答案正确... 0ms

├ 测试数据 25：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

快速幂的矩阵乘法优化状态压缩DP