ASC1 E Nice Patterns Strike Back-白红宇

ASC1 E Nice Patterns Strike Back

阅读量：4947 次

发布时间：2019-06-11

本文共 3017 字，大约阅读时间需要 10 分钟。

题意:给你N×（1-5）的格子，每一个格子有两种颜色，其中2x2个格子内的颜色不能都相同。

解题思路：状态压缩+ 矩阵快速幂 +大数。

解题代码：

1 // File Name: e.cpp  2 // Author: darkdream  3 // Created Time: 2015年03月21日 星期六 19时58分58秒  4   5 #include
      
         6 #include
       
          7 #include
          8 #include
         
            9 #include
          
            10 #include
           
             11 #include
            
              12 #include
             
               13 #include
              
                14 #include
               
                 15 #include
                
                  16 #include
                 
                   17 #include
                  
                    18 #include
                   
                     19 #include
                    
                      20 #include
                     
                       21 #include
                      
                        22 #include
                       
                         23 #include
                        
                          24 #define LL long long 25 26 using namespace std; 27 int M , n ; 28 struct Matrix 29 { 30 int mat[40][40]; 31 void clear() 32 { 33 memset(mat,0,sizeof(mat)); 34 } 35 void output() 36 { 37 for(int i = 0 ;i < n;i ++) 38 { 39 for(int j = 0 ;j < n;j ++) 40 { 41 printf("%d ",mat[i][j]); 42 } 43 printf("\n"); 44 } 45 } 46 Matrix operator *(const Matrix &b) const 47 { 48 Matrix ret; 49 ret.clear(); 50 for(int i = 0 ;i < n;i ++) 51 for(int j = 0 ;j < n;j ++) 52 { 53 for(int s = 0 ; s < n; s ++) 54 { 55 ret.mat[i][j] = (ret.mat[i][j] + mat[i][s] *b.mat[s][j] % M) % M; 56 } 57 } 58 return ret; 59 } 60 }a; 61 char str[1000]; 62 int num[1000]; 63 int len ; 64 int t; 65 void judge(int x, int y) 66 { 67 //printf("%d %d***\n",x,y); 68 int tx = x; 69 int ty = y; 70 int ttt = 0 ; 71 int txa[10]; 72 int tya[10]; 73 memset(txa,0,sizeof(txa)); 74 memset(tya,0,sizeof(tya)); 75 while(tx) 76 { 77 txa[ttt] = tx % 2; 78 tx/= 2; 79 ttt++; 80 } 81 ttt =0 ; 82 while(ty) 83 { 84 tya[ttt] = ty % 2; 85 ty /= 2; 86 ttt++; 87 } 88 for(int i = 1;i < t; i ++) 89 if(tya[i]+tya[i-1]+txa[i] + txa[i-1] == 4 || tya[i] + tya[i-1] + txa[i] + txa[i-1] == 0 ) 90 { 91 return; 92 } 93 a.mat[x][y] = 1; 94 } 95 void jian() 96 { 97 for(int i= 0 ;i <= len/2;i ++) 98 { 99 swap(num[i],num[len-i]); 100 }101 for(int i = 0 ;i <= len ;i ++)102 {103 if(num[i] == 0 )104 {105 num[i] = 9 ;106 }else{107 num[i]-- ;108 break;109 }110 }111 /*for(int i = len ;i >= 0 ;i --)112 printf("%d",num[i]);113 printf("\n");*/114 if(num[len] == 0 )115 len --;116 /*117 for(int i = len ;i >= 0 ;i --)118 printf("%d",num[i]);119 printf("\n");*/120 }121 void chu()122 {123 int tmp = 0 ; 124 for(int i = len ;i >= 0 ;i --)125 {126 int k = (tmp * 10 + num[i]);127 num[i] = k/2;128 tmp = k % 2; 129 }130 if(num[len] == 0 )131 len --;132 /*133 for(int i = len ;i >= 0 ;i --)134 printf("%d",num[i]);135 printf("\n");*/136 }137 Matrix Pow(Matrix a)138 {139 Matrix ret;140 ret.clear();141 for(int i= 0 ;i < n;i ++)142 ret.mat[i][i] = 1;143 Matrix tmp = a; 144 while(len != -1)145 {146 // printf("%d ***\n",len);147 if(num[0] % 2 == 1)148 {149 ret = ret * tmp ;150 //ret.output();151 }152 tmp = tmp*tmp ;153 chu();154 }155 return ret; 156 }157 int main(){158 freopen("nice.in","r",stdin);159 freopen("nice.out","w",stdout);160 161 scanf("%s %d %d",str,&t,&M);162 len = strlen(str);163 for(int i= 0 ;i < len ;i ++)164 {165 num[i] = str[i] - '0';166 }167 len --; 168 n = (1 << t);169 for(int i = 0 ;i