| Time Limit: 3000MS | Memory Limit: Unknown | 64bit IO Format: %lld & %llu |
Description
|
I I U P C 2 0 0 6 |
|
|
Problem H: How many Knight Placing? |
|
|
Input: standard input Output: standard output |
|
|
You are given a 6*n chessboard. Yes it is not a regular chessboard. The number of columns in this chessboard is variable. In each of the columns you have to place exactly 2 knights. So you have to place total 2*n knights. You have to count the number of valid placing of these 2*n knight. A placing is invalid if any of the 2 knights attack each other. Those who are not familiar with knight moves “A knight in cell(x,y) attacks the knights in the cell(x±2,y±1) and cell(x±1,y±2)”. |
|
|
Input |
|
|
The first line of the input contains a single integer T indicating the number of test cases. Each test case contains a single integer n. |
|
|
Output |
|
|
For each test case output an integer the number of valid placing. The integer may be very large. So just output the result%10007. |
|
|
Constraints |
|
|
- T ≤ 15 |
|
|
Sample Input |
Output for Sample Input |
|
4 |
15 |
好恶心的矩阵构造啊！
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define mod 10007
typedef struct point
{
int x,y;
} point;
typedef struct mar
{
int a[][];
} mar;
mar ri,anss,riri;
point p[];
int a[];
int check(int t)
{
int sum=;
while(t)
{
if(t&)sum++;
t>>=;
}
return sum==;
}
bool fun(int x,int y)
{
if((x<<)&y||(y<<)&x)return ;
return ;
}
bool fun1(int x,int y,int z)
{
if(!fun(x,y)||!fun(y,z))return ;
if((x<<)&z||(z<<)&x)return ;
return ;
}
mar mul(mar x,mar y)
{
mar z;
memset(z.a,,sizeof(z.a));
int i,j,k;
for(k=; k<; k++)
for(i=; i<; i++)
if(x.a[i][k])
for(j=; j<; j++)
z.a[i][j]+=x.a[i][k]*y.a[k][j]%mod,z.a[i][j]%=mod;
return z;
}
void init()
{
int tt=(<<)-,nu=,i,j;
while(tt)
{
if(check(tt))
a[nu++]=tt;
tt--;
}
nu=;
for(i=; i<; i++)
for(j=; j<; j++)
if(fun(a[i],a[j]))
p[nu].x=a[i],p[nu++].y=a[j];
memset(ri.a,,sizeof(ri.a));
for(i=; i<; i++)
{
for(j=; j<; j++)
{
if(p[i].y==p[j].x)
{
if(fun1(p[i].x,p[i].y,p[j].y))
ri.a[i][j]=;
}
}
}
}
int solve(int m)
{
int i,j,ans=;
memset(anss.a,,sizeof(anss.a));
memset(riri.a,,sizeof(riri.a));
for(i=; i<; i++)anss.a[i][i]=;
for(i=; i<; i++)
for(j=; j<; j++)riri.a[i][j]=ri.a[i][j];
m-=;
while(m)
{
if(m&)
anss=mul(anss,riri);
riri=mul(riri,riri);
m>>=;
}
for(i=; i<; i++)
for(j=; j<; j++)ans+=anss.a[i][j],ans%=mod;
return ans;
}
int main()
{
init();
int t,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
if(m==)
{
printf("15\n");
continue;
}
else if(m==)
{
printf("69\n");
continue;
}
printf("%d\n",solve(m));
}
}