sgu 197 Nice Patterns Strike Back-白红宇

sgu 197 Nice Patterns Strike Back

阅读量：4684 次

发布时间：2019-06-09

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

题意：铺马路，不出现2*2的同颜色的方格的方案数。

由于m很小，因此一行最多有32种涂法。而一行的涂法是从上一行转移过来的。比如：

m=2时，0表示白砖，1黑砖。

A:00,B:10,C:01,D:11

A B C D

A 0 1 1 1

B 1 1 1 1

C 1 1 1 1

D 1 1 1 0

i行j列为1表示第k-1行为j状态时，第k行能转移到i状态。这个矩阵相当于斐波那契中的{1,1,1,0}矩阵。也是描述转移的。用这个矩阵快速幂。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define mkp make_pairusing namespace std;const double EPS=1e-8;typedef long long lon;const int SZ=50,INF=0x7FFFFFFF;lon arr[SZ][SZ];int m,mod;string n;bool chk(int x,int y,int m){ int res1=x|y; for(int i=0;i+1
                 
                   num2[i]) { blag = 0; // 标记结果为正数 break; } else { blag = 1; // 标记结果为负数 // 交换两个数，便于计算 temp = num1; num1 = num2; num2 = temp; break; } } } len = len1>len2 ? len1 : len2; // 获取较大的位数 //将num1字符数组的数字转换为整型数且逆向保存在整型数组sum中，即低位在前，高位在后 for (i = len1-1, j = 0; i >= 0; i--, j++) sum[j] = num1[i] - '0'; // 转换第二个数 for (i = len2-1, j = 0; i >= 0; i--, j++) n2[j] = num2[i] - '0'; // 将两个大数相减 for (i = 0; i <= len; i++) { sum[i] = sum[i] - n2[i]; // 两个数从低位开始相减 if (sum[i] < 0) // 判断是否有借位 { // 借位 sum[i] += 10; sum[i+1]--; } } // 计算结果长度 for (i = len1-1; i>=0 && sum[i] == 0; i--) ; len = i+1; if(blag==1) { sum[len] = -1; // 在高位添加一个-1表示负数 len++; } return len; // 返回结果的位数 }void init(){ cin>>n>>m>>mod; char tmp[200],one[]={ '1',0}; copy(n.begin(),n.end(),tmp); tmp[n.size()]=0; int res[200]; int sz=Subtraction(tmp,one,res); for(int i=sz-1;i>=0;--i) { tmp[sz-i-1]=res[i]+'0'; } tmp[sz]=0; n.assign(tmp); //cout<
                  
                   <<" "<
                   
                    <
                    
                      p2 for(i = len1-1; i >= 0; i--) { if(p1[i] > p2[i]) // 若大，则满足条件，可做减法 break; else if(p1[i] < p2[i]) // 否则返回-1 return -1; } } for(i = 0; i <= len1-1; i++) // 从低位开始做减法 { p1[i] -= p2[i]; // 相减 if(p1[i] < 0) // 若是否需要借位 { // 借位 p1[i] += 10; p1[i+1]--; } } for(i = len1-1; i >= 0; i--) // 查找结果的最高位 { if( p1[i] ) //最高位第一个不为0 return (i+1); //得到位数并返回 } return 0; //两数相等的时候返回0}int Division(char a1[]){ int DVN=2; int a[102],x=0,c[102]; int L=strlen(a1),L1=1; int i,j; for(i=1;i<=L;i++) a[i]=a1[i-1]-'0';//???????,?????? for(i=1;i<=L;i++) { c[i]=(x*10+a[i])/DVN; x=(x*10+a[i])%DVN;//????? } while(c[L1]==0&&L1
                     
                      >casenum; //for(lon time=1;time<=casenum;++time) { init();// if(n=="1"&&m==2&&mod==5)// {// for(int i=0;i<100000;++i)++arr[i][i];// } if(n=="0"&&m==1) { cout<<2%mod<