tkdsheep-ZOJ2317
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
给N*M的格子，N非常大，M小于等于5，然后对格子黑白染色，使得任意一个2*2的区域的4个格子颜色不能完全相同，问总的方案数
很明显是矩阵乘法，dp[mask]来表示当前行，黑白染色状态是mask的情况下，有多少种方案，这个方案只与上一行的mask有关
然后逐一check两种mask之间是否合法，建立转移矩阵即可
然后此题的N是10^100
于是我用了JAVA来写蛋疼的大数。。非常蛋疼。。而且时限卡的很紧，优化不好就超时，模板我依然用的是好基友、前队友delta的矩阵乘法模板，在JAVA下面改了一下语法格式，也算练练手吧
另外此题中矩阵乘法尽量少用mod，我是参照shi哥的做法，最后才mod的，因为题中mod最大值为10000，所以用long就可以避免爆掉
shi哥的矩阵求幂写法也值得学习，代码中有注释
}}}
{{{
import java.util.*;
import java.math.*;
public class Main {
static int unit[]={1,2,4,8,16,32,64};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
BigInteger N;
int M,P,i,j,k;
long c[][]=new long[32][32];
long ans[][]=new long[32][32];
long s[][]=new long[32][32];
int re=in.nextInt();
while(re>0){
re--;
N=in.nextBigInteger();
M=in.nextInt();
P=in.nextInt();
for(i=0;i<32;i++)
for(j=0;j<32;j++)
s[i][j]=c[i][j]=ans[i][j]=0;
for(i=0;i<unit[M];i++)
{
s[i][i]=1;
ans[0][i]=1;
}
for(j=0;j<unit[M];j++)
{
for(i=0;i<unit[M];i++)
{
if(check(i,j,M))
c[i][j]=1;
}
}
/*N=N.subtract(BigInteger.ONE);
for(i=N.bitLength()-1;i>=0;--i){//orz watashi~ learn from shi ge
matrix_mul(unit[M],s,s,P);
if(N.testBit(i)){
matrix_mul(unit[M],s,c,P);
}
}*/
matrix_binary_exp(unit[M], c, N.subtract(BigInteger.ONE), P);
matrix_mul(unit[M], ans, c, P);
//matrix_mul(unit[M], ans, s, P);
long res=0;
for(i=0;i<unit[M];i++)
res=(res+ans[0][i])%P;
System.out.println(res);
if(re>0)
System.out.println();
}
}
public static boolean check(int x,int y,int M){
for(int i=0;i<M-1;i++)
{
if((unit[i]&x)>0&&(unit[i+1]&x)>0&&(unit[i]&y)>0&&(unit[i+1]&y)>0)
return false;
if((unit[i]&x)==0&&(unit[i+1]&x)==0&&(unit[i]&y)==0&&(unit[i+1]&y)==0)
return false;
}
return true;
}
public static void matrix_mul(int n, long x[][], long y[][], int MOD) {
int i, j, k;
long tmp[][]=new long[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
tmp[i][j]=0;
for (i=0; i<n; ++i) for (j=0; j<n; ++j) for (k=0; k<n; ++k) {
tmp[i][j] = (tmp[i][j] + x[i][k] * y[k][j]);
}
for (i=0; i<n; ++i) for (j=0; j<n; ++j) x[i][j] = tmp[i][j]%MOD;
}
public static void matrix_binary_exp(int n, long x[][], BigInteger exp, int MOD) {
int i, j, k;
long tmp[][]=new long [n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
tmp[i][j]=0;
for (i=0; i<n; ++i) tmp[i][i] = 1;
while (!exp.equals(BigInteger.ZERO)) {
if (exp.mod(BigInteger.valueOf(2)).equals(BigInteger.ONE)) matrix_mul(n, tmp, x, MOD);
matrix_mul(n, x, x, MOD);
exp=exp.divide(BigInteger.valueOf(2));
}
for (i=0; i<n; ++i) for (j=0; j<n; ++j) x[i][j] = tmp[i][j];
}
}
}}}给N*M的格子，N非常大，M小于等于5，然后对格子黑白染色，使得任意一个2*2的区域的4个格子颜色不能完全相同，问总的方案数
很明显是矩阵乘法，dp[mask]来表示当前行，黑白染色状态是mask的情况下，有多少种方案，这个方案只与上一行的mask有关
然后逐一check两种mask之间是否合法，建立转移矩阵即可
然后此题的N是10^100
于是我用了JAVA来写蛋疼的大数。。非常蛋疼。。而且时限卡的很紧，优化不好就超时，模板我依然用的是好基友、前队友delta的矩阵乘法模板，在JAVA下面改了一下语法格式，也算练练手吧
另外此题中矩阵乘法尽量少用mod，我是参照shi哥的做法，最后才mod的，因为题中mod最大值为10000，所以用long就可以避免爆掉
shi哥的矩阵求幂写法也值得学习，代码中有注释
import java.util.*;
import java.math.*;
public class Main {
static int unit[]={1,2,4,8,16,32,64};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
BigInteger N;
int M,P,i,j,k;
long c[][]=new long[32][32];
long ans[][]=new long[32][32];
long s[][]=new long[32][32];
int re=in.nextInt();
while(re>0){
re--;
N=in.nextBigInteger();
M=in.nextInt();
P=in.nextInt();
for(i=0;i<32;i++)
for(j=0;j<32;j++)
s[i][j]=c[i][j]=ans[i][j]=0;
for(i=0;i<unit[M];i++)
{
s[i][i]=1;
ans[0][i]=1;
}
for(j=0;j<unit[M];j++)
{
for(i=0;i<unit[M];i++)
{
if(check(i,j,M))
c[i][j]=1;
}
}
/*N=N.subtract(BigInteger.ONE);
for(i=N.bitLength()-1;i>=0;--i){//orz watashi~ learn from shi ge
matrix_mul(unit[M],s,s,P);
if(N.testBit(i)){
matrix_mul(unit[M],s,c,P);
}
}*/
matrix_binary_exp(unit[M], c, N.subtract(BigInteger.ONE), P);
matrix_mul(unit[M], ans, c, P);
//matrix_mul(unit[M], ans, s, P);
long res=0;
for(i=0;i<unit[M];i++)
res=(res+ans[0][i])%P;
System.out.println(res);
if(re>0)
System.out.println();
}
}
public static boolean check(int x,int y,int M){
for(int i=0;i<M-1;i++)
{
if((unit[i]&x)>0&&(unit[i+1]&x)>0&&(unit[i]&y)>0&&(unit[i+1]&y)>0)
return false;
if((unit[i]&x)==0&&(unit[i+1]&x)==0&&(unit[i]&y)==0&&(unit[i+1]&y)==0)
return false;
}
return true;
}
public static void matrix_mul(int n, long x[][], long y[][], int MOD) {
int i, j, k;
long tmp[][]=new long[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
tmp[i][j]=0;
for (i=0; i<n; ++i) for (j=0; j<n; ++j) for (k=0; k<n; ++k) {
tmp[i][j] = (tmp[i][j] + x[i][k] * y[k][j]);
}
for (i=0; i<n; ++i) for (j=0; j<n; ++j) x[i][j] = tmp[i][j]%MOD;
}
public static void matrix_binary_exp(int n, long x[][], BigInteger exp, int MOD) {
int i, j, k;
long tmp[][]=new long [n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
tmp[i][j]=0;
for (i=0; i<n; ++i) tmp[i][i] = 1;
while (!exp.equals(BigInteger.ZERO)) {
if (exp.mod(BigInteger.valueOf(2)).equals(BigInteger.ONE)) matrix_mul(n, tmp, x, MOD);
matrix_mul(n, x, x, MOD);
exp=exp.divide(BigInteger.valueOf(2));
}
for (i=0; i<n; ++i) for (j=0; j<n; ++j) x[i][j] = tmp[i][j];
}
}