SGU197 给N*M的格子涂黑白两种颜色，要求没有2*2的小矩形是同色的。 N很大，M很小。 答案对P取模。 明显的状态压缩出转移，然后矩阵优化下就可以了。
197. Nice Patterns Strike Back
time limit per test: 0.5 sec. memory limit per test: 65536 KB
input: standard output: standard
You might have noticed that there is the new fashion among rich people to have their yards tiled with black and white tiles, forming a pattern. The company Broken Tiles is well known as the best tiling company in our region. It provides the widest choices of nice patterns to tile your yard with. The pattern is nice if there is no square of size 2 × 2, such that all tiles in it have the same color. So patterns on the figure 1 are nice, while patterns on the figure 2 are not.
The president of the company wonders whether the variety of nice patterns he can provide to the clients is large enough. Thus he asks you to find out the number of nice patterns that can be used to tile the yard of size N × M. Now he is interested in the long term estimation, so he suggests N ≤ 10100. However, he does not like big numbers, so he asks you to find the answer modulo P.
Input
The input file contains three integer numbers: N (1 ≤ N ≤ 10100), M (1 ≤ M ≤ 5) and P (1 ≤ P ≤ 10000).
Output
Write the number of nice patterns of size N × M modulo P to the output file.
Sample test(s)
Input
Test #1 2 2 5 Test #2 3 3 23
Output
Test #1 4 Test #2 0
import java.util.;
import java.math.;
public class Solution
{
static int P;
static Matrix pow_M(Matrix a,BigInteger n){
Matrix ret = new Matrix();
Matrix tmp = a;
ret.init(a.n,P);
for(int i = 0;i < a.n;i++)
ret.mat[i][i] = 1;
while(!n.equals(BigInteger.ZERO)){
if(n.mod(BigInteger.valueOf(2)).equals(BigInteger.ONE))
ret = ret.mul(tmp);
tmp = tmp.mul(tmp);
n = n.divide(BigInteger.valueOf(2));
}
return ret;
}
static boolean check(int s1,int s2,int n){
for(int i = 0;i < n-1;i++){
if( (s1&(1<<i)) == 0 && (s1&(1<<(i+1))) == 0
&& (s2&(1<<i)) == 0 && (s2&(1<<(i+1))) == 0)
return false;
if( (s1&(1<<i)) > 0 && (s1&(1<<(i+1))) > 0
&& (s2&(1<<i)) > 0 && (s2&(1<<(i+1))) > 0)
return false;
}
return true;
}
public static void main(String[] args)
{
// TODO Auto-generated method stub
Scanner cin = new Scanner(System.in);
BigInteger n;
int m;
while(cin.hasNext()){
n = cin.nextBigInteger();
m = cin.nextInt();
P = cin.nextInt();
Matrix a = new Matrix();
a.init(1<<m,P);
for(int i = 0;i < (1<<m);i++)
for(int j = 0;j < (1<<m);j++)
if(check(i,j,m))
a.mat[i][j] = 1;
a = pow_M(a,n.subtract(BigInteger.ONE));
int ans = 0;
for(int i = 0;i < (1<<m);i++)
for(int j = 0;j < (1<<m);j++){
ans = ans + a.mat[i][j];
ans = ans%P;
}
System.out.println(ans);
}
cin.close();
}
}
class Matrix{
static int P;
int [][]mat = new int[100][100];
int n;
void init(int _n,int _p){
n = _n;
P = _p;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
mat[i][j] = 0;
}
Matrix mul(Matrix b){
Matrix ret = new Matrix();
ret.init(n,P);
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++){
for(int k = 0;k < n;k++){
ret.mat[i][j] = ret.mat[i][j] + mat[i][k]*b.mat[k][j]%P;
ret.mat[i][j] %= P;
}
}
return ret;
}
}
