矩阵乘法是显然的
把末2位的状态分成4类：
S1：黑黑、红红、蓝蓝
S2：黑红、黑蓝、红黑、红蓝、蓝黑、蓝红
S3：白白、黑白、蓝白、红白
S4：白黑、白红、白蓝
则有
S'1=S4
S'2=S2+2S4
S'3=S1+S2+S3+S4
S'4=3S3
得到矩阵A
| 0 |
0 |
1 |
0 |
| 0 |
1 |
1 |
0 |
| 0 |
0 |
1 |
3 |
| 1 |
2 |
1 |
0 |
直接做矩阵乘法居然超时，时限太BT了，所以我把要求的二进制数拆成三部分，预处理求出以下值
A
0,A
1,...,A
1023A
0,A
1024,...,A
1047552A
0,A
1048576,...,A
1072693248
然后对于每个询问，只用求三个矩阵的乘积即可
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int mo=1000000007;
const int c[4][4]={{0,0,1,0},
{0,1,1,0},
{0,0,1,3},
{1,2,1,0}};
const int e[4][4]={{1,0,0,0},
{0,1,0,0},
{0,0,1,0},
{0,0,0,1}};
const int s[4]={3,6,4,3};
char st[20];
int f[32][4][4],res1[1024][4][4],res2[1024][4][4],res3[1024][4][4],a[4][4],b[4][4];
void multi(int a[4][4],int b[4][4],int c[4][4])
{
int i,j,k;
long long tmp;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
tmp=0;
for(k=0;k<4;k++)
tmp+=(long long)(a[i][k])*b[k][j];
c[i][j]=tmp%mo;
}
}
int getint(void)
{
gets(st);
int res=0;
for(int i=0;st[i]!='\0';i++)
if(st[i]>='0'&&st[i]<='9')
res=res*10+st[i]-48;
return res;
}
int main(void)
{
int k,i,j,u,n,ans;
long long tmp;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
f[0][i][j]=c[i][j];
res1[0][i][j]=res2[0][i][j]=res3[0][i][j]=e[i][j];
}
for(k=1;k<=20;k++)
multi(f[k-1],f[k-1],f[k]);
for(k=1;k<1024;k++)
multi(res1[k-1],f[0],res1[k]);
for(k=1;k<1024;k++)
multi(res2[k-1],f[10],res2[k]);
for(k=1;k<1024;k++)
multi(res3[k-1],f[20],res3[k]);
u=getint();
while(u--)
{
n=getint();
if (n==1)
{
printf("%d\n",4);
continue;
}
n-=2;
multi(res1[n&1023],res2[(n>>10)&1023],b);
multi(b,res3[(n>>20)&1023],a);
tmp=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
tmp+=(long long)(s[i])*a[i][j];
ans=tmp%mo;
printf("%d\n",ans);
}
return 0;
}
posted on 2010-10-01 23:50
zxb 阅读(184)
评论(0) 编辑 收藏 引用