1884.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 1884 on 2006-09-18 at 15:29:31 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 33;
const int K = 128;

int64 m[N][N][K];
int k;

int64 find(int, int, int, int);

int main()
{
	int T;
	
	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		int n; scanf("%d %d", &n, &k);
		printf("Case %d: ", t);
		int64 r;
		if((n&1) || k == 0) r = 0;
		else { memset(m, -1, sizeof(m)); r = find(n>>1, n>>1, 0, 0); }
		printf("%lld\n", r);
	}
	
	return 0;
}

int64 find(int zn, int on, int r, int d)
{
	if(zn+on == 0) return (r == 0) ? 1 : 0;
	if(m[zn][on][r] == -1) {
		m[zn][on][r] = 0;
		if(zn > 0 && d != 0) m[zn][on][r] += find(zn-1, on, (r*2)%k, d+1);
		if(on > 0) m[zn][on][r] += find(zn, on-1, (r*2+1)%k, d+1);
	}
	return m[zn][on][r];
}