首页 > 代码库 > ZOJ 2317 Nice Patterns Strike Back
ZOJ 2317 Nice Patterns Strike Back
题意
在一个N*M的矩阵中给每个格子染上黑白色，要求任意一个2*2的矩阵颜色不能一样，N<=10^100，m<=5。
解法
首先看这个题，若n和m很小，则我们可以直接用状态压缩乱搞，但是N太大了，显然只能是快速幂（看到这个题的第一感觉），然后就是构造矩阵，在矩阵快速幂，不说了，网上说的比我好的太多了。这个题我并不想写这个博客的，但是由于它是我第一个java程序（虽然以前写过一个，不过那个是a+b问题），所以纪念一下
import java.util.*;import java.math.*;class Matrix{ public long [][] a; public int n; Matrix (int x) { n = x; a = new long [n][n]; for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j]=0; }}public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int T,m,p; BigInteger n; T = cin.nextInt(); while((T--)>0) { n = cin.nextBigInteger(); m = cin.nextInt(); p = cin.nextInt(); Matrix A = new Matrix(1<<m); for (int i=0;i<(1<<m);i++) { for (int j=0;j<(1<<m);j++) if (ok(i,j,m)==1) A.a[i][j]=1; else A.a[i][j]=0; } n = n.subtract(BigInteger.ONE); A = ML(A,n,m,p); long ans=0; for (int i=0;i<(1<<m);i++) for (int j=0;j<(1<<m);j++) ans=(ans+A.a[i][j])%p; System.out.println(ans); if (T>0) System.out.println(); } cin.close(); } public static int ok(int x,int y,int s) { for (int i=s-1;i>0;i--) { int b1 = (((1<<i)&x) > 0) ? 1 : 0; int b2 = (((1<<i)&y) > 0) ? 1 : 0; int b3 = (((1<<(i-1))&x) > 0) ? 1: 0; int b4 = (((1<<(i-1))&y) > 0) ? 1: 0; if (b1==b2 && b2==b3 && b3==b4) return 0; } return 1; } public static Matrix M_L(Matrix A,Matrix B,int n,int p) { Matrix temp = new Matrix(1<<n); for (int i=0;i<(1<<n);i++) for (int j=0;j<(1<<n);j++) for (int k=0;k<(1<<n);k++) temp.a[i][j]+=((A.a[i][k]*B.a[k][j])%p); return temp; } public static Matrix ML(Matrix A,BigInteger n,int m,int p) { Matrix temp = new Matrix(1<<m); for (int i=0;i<(1<<m);i++) for (int j=0;j<(1<<m);j++) if (i==j) temp.a[i][j]=1; while(!n.equals(BigInteger.ZERO)) //快速幂 { if((n.and(BigInteger.ONE)).equals(BigInteger.ONE)) { temp=M_L(temp, A, m, p); } A = M_L(A, A, m, p); n = n.shiftRight(1); } return temp; }}
ZOJ 2317 Nice Patterns Strike Back
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。