SGU 208 Toral Tickets（polay计数）-白红宇

SGU 208 Toral Tickets（polay计数）

阅读量：6160 次

发布时间：2019-06-21

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

题目链接：

题意：在一个n*m的格子上进行黑白染色。染色完后将长边卷起来卷成一个圆柱体，然后把圆柱体的上下两个圆拼起来得到一个类似游泳圈形状的东西。求有多少种不同的游泳圈?

思路：首先，n行上下可以转动，m列左右可以转动，还可以上下翻转180度，共n*m*2种。另外，若n==m，则还可以翻转90度和270度，此时有n*m*4种。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define FOR0(i,x) for(i=0;i
                
                 =0;i--)#define DOW1(i,x) for(i=x;i>=1;i--)#define DOW(i,a,b) for(i=a;i>=b;i--)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%I64d",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%d\n",x);}void PR(i64 x) {printf("%I64d\n",x);}void PR(u32 x) {printf("%u\n",x);}void PR(double x) {printf("%.4lf\n",x);}void PR(char x) {printf("%c\n",x);}void PR(char *x) {printf("%s\n",x);}void PR(string x) {cout<
                 
                  <
                  
                   temp.a[0]) p=a[0]; else p=temp.a[0]; for(i=a[0],j=temp.a[0],k=p;j>=1&&i>=1;i--,j--,k--) ans.a[k]=a[i]+temp.a[j]; if(j==0) { while(i>=1) ans.a[i]=a[i--]; } else { while(j>=1) ans.a[j]=temp.a[j--]; } ans.a[0]=0; for(i=p;i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=p+1;i>=1;i--) ans.a[i]=ans.a[i-1]; ans.a[0]=p+1; } else ans.a[0]=p; return ans; } BigNum operator-(BigNum temp) { BigNum ans; int i,j; for(i=0;i<=a[0];i++) ans.a[i]=a[i]; for(i=ans.a[0],j=temp.a[0];i>=1&&j>=1;i--,j--) ans.a[i]-=temp.a[j]; for(i=ans.a[0];i>=1;i--) if(ans.a[i]<0) { ans.a[i]+=MOD; ans.a[i-1]--; } for(i=1;i<=a[0];i++) if(ans.a[i]) break; if(i>a[0]) { ans.a[0]=1; ans.a[1]=0; return ans; } for(j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j]; ans.a[0]=a[0]-i+1; return ans; } BigNum operator*(BigNum temp) { BigNum ans; int i,j,p=a[0]+temp.a[0]-1; memset(ans.a,0,sizeof(ans.a)); for(i=a[0];i>=1;i--) for(j=temp.a[0];j>=1;j--) ans.a[i+j-1]+=a[i]*temp.a[j]; ans.a[0]=0; for(i=p;i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=p;i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]=p+1; } else ans.a[0]=p; return ans; } BigNum operator*(int temp) { BigNum ans; int i; for(i=1;i<=a[0];i++) ans.a[i]=a[i]*temp; ans.a[0]=0; for(i=a[0];i>=1;i--) { ans.a[i-1]+=ans.a[i]/MOD; ans.a[i]%=MOD; } if(ans.a[0]) { for(i=a[0];i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]=a[0]+1; } else ans.a[0]=a[0]; if(ans.a[1]>=MOD) { for(i=ans.a[0];i>=0;i--) ans.a[i+1]=ans.a[i]; ans.a[0]++; } return ans; } BigNum operator/(int x) { BigNum ans; int i,j; i64 p; for(i=1;i<=a[0];i++) { if(i==1) { ans.a[i]=a[i]/x; p=a[i]%x; } else { ans.a[i]=(p*MOD+a[i])/x; p=(p*MOD+a[i])%x; } } for(i=1;i<=a[0];i++) if(ans.a[i]) break; if(i>a[0]) { ans.a[0]=1; ans.a[1]=0; return ans; } for(j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j]; ans.a[0]=a[0]-i+1; return ans; } BigNum operator/(BigNum temp) { BigNum ans,t; BigNum low=BigNum(1),high,mid; int i; for(i=1;i<=a[0];i++) t.a[i]=high.a[i]=a[i]; t.a[0]=high.a[0]=a[0]; while(!(low>high)) { mid=(low+high)/2; if(mid*temp>t) high=mid-BigNum(1); else low=mid+BigNum(1); } if(!(low>t)&&!(temp*low>t)) return low; return high; } BigNum operator%(BigNum temp) { int i; BigNum t; for(i=1;i<=a[0];i++) t.a[i]=a[i]; t.a[0]=a[0]; return t-t/temp*temp; } BigNum power(int n) { BigNum ans=BigNum(1),temp=*this; while(n) { if(n&1) ans=ans*temp; temp=temp*temp; n>>=1; } return ans; } public: BigNum() { a[0]=1; a[1]=0; } BigNum(int x) { if(x>=MOD) a[0]=2,a[1]=x/MOD,a[2]=x%MOD; else a[0]=1,a[1]=x; } BigNum(i64 x) { stack
                   
                     s; while(x) { s.push(x%MOD); x/=MOD; } a[0]=s.size(); int k=0; while(!s.empty()) { a[++k]=s.top(); s.pop(); } } BigNum(string str) { int i; for(i=0;i
                    
                     (BigNum temp) { if(a[0]>temp.a[0]) return 1; if(a[0]
                     
                      temp.a[i]; return 0; } void print() { int i=1; while(i<=a[0]&&a[i]==0) i++; if(i>a[0]) { puts("0"); return; } printf("%lld",a[i++]); while(i<=a[0]) printf("%07lld",a[i++]); } };const int N=25;int n,m,g[N][N];BigNum ans;void copy(int a[N][N],int b[N][N]){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { a[i][j]=b[i][j]; }}void down(int a[N][N]){ int i,j; for(i=1;i<=m;i++) a[0][i]=a[n][i]; for(i=n;i>=1;i--) for(j=1;j<=m;j++) { a[i][j]=a[i-1][j]; }}void right(int a[N][N]){ int i,j; for(i=1;i<=n;i++) a[i][0]=a[i][m]; for(i=1;i<=n;i++) for(j=m;j>=1;j--) { a[i][j]=a[i][j-1]; }}void rotate(int a[N][N]){ int b[N][N],i,j; copy(b,a); for(i=1;i<=m;i++) for(j=n;j>=1;j--) { a[i][n+1-j]=b[j][i]; } swap(n,m);}int cal(int a[N][N]){ int visit[N*N]={0},b[N*N],i,j,k,cnt=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { b[(i-1)*m+j]=a[i][j]; } for(i=1;i<=n*m;i++) if(!visit[i]) { cnt++; visit[i]=1; k=b[i]; while(k!=i) visit[k]=1,k=b[k]; } return cnt;}int main(){ RD(n,m); if(n>m) swap(n,m); int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { g[i][j]=(i-1)*m+j; } int a[N][N]; for(i=1;i<=n;i++) { copy(a,g); for(j=1;j<=m;j++) { ans=ans+BigNum(2).power(cal(a)); rotate(a); if(n==m) ans=ans+BigNum(2).power(cal(a)); rotate(a); ans=ans+BigNum(2).power(cal(a)); rotate(a); if(n==m) ans=ans+BigNum(2).power(cal(a)); rotate(a); right(a); } down(g); } ans=ans/(n*m*2); if(n==m) ans=ans/2; ans.print(); puts(""); return 0;}

转载地址：http://weafa.baihongyu.com/

你可能感兴趣的文章

好记性不如烂笔杆-android学习笔记<十六> switcher和gallery