• https://codeforces.com/problemsets/acmsguru/submission/99999/205409750
• https://vjudge.net/problem/SGU-208

题意

给定一个 n∗m 的单面方格纸，然后把方格纸的长边卷起来，卷成一个圆柱体，再把收尾也接起来，形成一个 torus。求对格点进行黑白染色的方案数。

分析

Polya 计数，数据范围很小，暴力做循环分解即可。
难点是对于 n == m 的情况，要考虑 rt90()。

#include <lastweapon/bignum>
using namespace lastweapon;

const int N = 20;
int a[N][N], b[N][N]; bool v[N][N];
int n, m; bignum z;

int f(){
	int z = 0; RST(v);
	REP(i, n) REP(j, m) if (!v[i][j]) {
        int x = i, y = j;  do {
            v[x][y] = true;  int t = a[x][y];
            x = t / m, y = t % m;
        } while (!v[x][y]);
        ++z;
    }
	return z;

}

void rt90(){
	CPY(b, a); REP(i, n) REP(j, m) a[j][n-i-1] = b[i][j];
	swap(n, m);
}

void rt180(){
	rt90(); rt90();
}

void rolln(){
	CPY(b, a); REP(i, n) REP(j, m) a[i][j] = b[(i+1)%n][j];
}

void rollm(){
	CPY(b, a); REP(i, n) REP(j, m) a[i][j] = b[i][(j+1)%m];
}

void init(){
	REP(i, n) REP(j, m) a[i][j] = i*m + j; z = 0;
}

void Polay(){
	if (n==m){
		for (int k=0;k<4;k++,rt90())
			for (int i=0;i<n;i++,rolln())
				for (int j=0;j<m;j++,rollm())
					z += pow(bignum(2), f());
		z /= 4*n*m;
	}
	else {
		for (int k=0;k<2;k++,rt180())
			for (int i=0;i<n;i++,rolln())
				for (int j=0;j<m;j++,rollm())
					z += pow(bignum(2), f());
		z /= 2*n*m;
	}
}

int main() {

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    while (scanf("%d %d", &n, &m) != EOF){
		init(); Polay();
		cout << z << endl;
	}
}

Posted by xiaodao
Category: 日常