Zoj 2344 Toral Tickets (数学_Polya)(五)

2014-11-24 10:45:28 · 作者: · 浏览: 6

}


return tot;
}
void UpMove(int arr[][MAX]) {

memcpy(arr[n+1],arr[1],sizeof(arr[1]));
for (int i = 2; i <= n; ++i)
memcpy(arr[i-1],arr[i],sizeof(arr[i]));
memcpy(arr[n],arr[n+1],sizeof(arr[n+1]));
}
void LeftMove(int arr[][MAX]) {

int i,j,k;
for (i = 1; i <= n; ++i)
arr[i][m+1] = arr[i][1];
for (j = 2; j <= m; ++j)
for (i = 1; i <= n; ++i)
arr[i][j-1] = arr[i][j];
for (i = 1; i <= n; ++i)
arr[i][m] = arr[i][1+m];
}
void Rotate(int arr[][MAX]) {

int i,j,k,brr[MAX][MAX];
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
brr[j][n+1-i] = arr[i][j];
memcpy(arr,brr,sizeof(brr));
k = n,n = m, m = k;
}
void Print(int arr[][MAX]) {

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
printf("%d%c",arr[i][j],j==m '\n':' ');
}
BigNum Power(int n,int k) {

BigNum x = n,ans = 1;
while (k) {

if (k & 1) ans = x * ans;
x = x * x,k >>= 1;
}
return ans;
}


int main()
{
int i,j,k,ii,jj,tp;


while (scanf("%d%d",&n,&m) != EOF) {

if (n > m) k = n,n = m,m = k;
memset(arr,0,sizeof(arr));
memset(cnt,0,sizeof(cnt));
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
arr[i][j] = j + (i - 1) * m;


for (ii = 1; ii <= n; ++ii) {

memcpy(temp,arr,sizeof(arr));
for (jj = 1; jj <= m; ++jj) {

tp = Calculate(temp); //0度
cnt[tp]++;
Rotate(temp); //90度
if (n == m)
tp = Calculate(temp),cnt[tp]++;
Rotate(temp); //180度
tp = Calculate(temp);
cnt[tp]++;


Rotate(temp); //270度
if (n == m)
tp = Calculate(temp),cnt[tp]++;
Rotate(temp); //360度
LeftMove(temp);
}
UpMove(arr);
}


BigNum ans = 0;
for (i = 1; i <= n * m; ++i)
if (cnt[i]) ans = ans + Power(2,i) * cnt[i];
if (n != m) ans = ans / (2 * n * m);
else ans = ans / (4 * n * m);
ans.print();
}
}