棋盘覆盖问题
刚开始 用最暴力的方法进行分割覆盖感觉要出一个答案 要很久,然后进行一次预处理就ok了 然后就很快了 ,这个重复覆盖是有规律的 然后我就将他们mod了个10086然后就ok了
#include <iostream> #include<string.h> #include<cstdio> using namespace std; struct point { int x,y,k; point(int a=0,int b=0,int c=0) { x=a;y=b,k=c; } }; int num[4]; int dp[34][4][4]; void judget(point T,point &A) { int i; T.k--; if(T.x<=((1<<T.k)-1)&&T.y<=((1<<T.k)-1)) { A=T; num[2]++; for(i=0;i<4;i++) { num[i]=(num[i]+dp[T.k][1][i])%10086; num[i]=(num[i]+dp[T.k][3][i])%10086; num[i]=(num[i]+dp[T.k][0][i])%10086; } return ; } if(T.x<=((1<<T.k)-1)&&T.y>((1<<T.k)-1)) { T.y=T.y-(1<<(T.k)); A=T;num[1]++; for(i=0;i<4;i++) { num[i]=(num[i]+dp[T.k][3][i])%10086; num[i]=(num[i]+dp[T.k][0][i])%10086; num[i]=(num[i]+dp[T.k][2][i])%10086; } return ; } if(T.x>((1<<T.k)-1)&&T.y<=((1<<T.k)-1)) { T.x-=(1<<T.k); A=T; num[3]++; for(i=0;i<4;i++) { num[i]=(num[i]+dp[T.k][2][i])%10086; num[i]=(num[i]+dp[T.k][0][i])%10086; num[i]=(num[i]+dp[T.k][1][i])%10086; } return ; } T.x-=(1<<T.k); T.y-=(1<<T.k); num[0]++; A=T; for(i=0;i<4;i++) { num[i]=(num[i]+dp[T.k][1][i])%10086; num[i]=(num[i]+dp[T.k][3][i])%10086; num[i]=(num[i]+dp[T.k][2][i])%10086; } return ; } void dfs(point T) { point Q; if(T.k==1) { if(T.x==0&&T.y==0) num[2]++; if(T.x==0&&T.y==1)num[1]++; if(T.x==1&&T.y==0)num[3]++; if(T.x==1&&T.y==1)num[0]++; return ; } judget(T,Q); dfs(Q); } int main() { int j,k,x,y,i,sum; memset(dp,0,sizeof(dp)); dp[1][0][2]=1; dp[1][1][3]=1; dp[1][2][0]=1; dp[1][3][1]=1; for(i=2;i<33;i++) for(j=0;j<4;j++) for(k=0;k<4;k++) { if(k==(j+2)%4) dp[i][j][k]=(dp[i][j][k]+1)%10086; dp[i][j][k]=(dp[i-1][(j+1)%4][k]+dp[i-1][(j+3)%4][k]+dp[i-1][j][k]*2+dp[i][j][k])%10086; } while(scanf("%d",&k)==1) { memset(num,0,sizeof(num)); scanf("%d%d",&x,&y); dfs(point(x,y,k)); cout<<num[0]<<‘ ‘<<num[3]<<‘ ‘<<num[1]<<‘ ‘<<num[2]<<endl; } return 0; }
?
?
?
?