学步园

【题意】

有n个方块，现用红黄蓝绿四种颜色将他们染色，要求红色的方块和蓝色的方块个数均为偶数个，求方案数 mod 10007

【输入】

第一行一个t，表示有t组数据

每组数据一个数字表示n

【输出】

对于每组数据，输出一个输出表示方案数

用一个2位的2进制数表示红色方块和蓝色方块的奇偶性，发现染i个的方案数只跟染i-1个的方案数有关

所以可以用矩阵来搞一搞

program poj3734;
type
  square=array [1..4,1..4] of longint;
const
  maxn=10007;
  root:square=((2,1,1,0),
               (1,2,0,1),
               (1,0,2,1),
               (0,1,1,2));
var
  ans:square;
  t,n,i:longint;

function matrixmul (a,b:square):square;
var
  i,j,k:longint;
  ans:square;
begin
  fillchar(ans,sizeof(ans),0);
  for i:=1 to 4 do
    for j:=1 to 4 do
      for k:=1 to 4 do
        ans[i,j]:=(ans[i,j]+a[i,k]*b[k,j]) mod maxn;
  exit(ans);
end;

function power (m:longint):square;
var
  ans,now:square;
begin
  now:=root;
  fillchar(ans,sizeof(ans),0);
  ans[1,1]:=1;
  ans[2,2]:=1;
  ans[3,3]:=1;
  ans[4,4]:=1;
  while m<>0 do
    begin
      if m and 1 = 1 then ans:=matrixmul(ans,now);
      m:=m div 2;
      now:=matrixmul(now,now);
    end;
  exit(ans);
end;

begin
  read(t);
  while t>0 do
    begin
      dec(t);
      read(n);
      ans:=power(n);
      writeln(ans[1,1]);
    end;
end.