Cod sursa(job #53875)

Utilizator grecoTiberiu-Lucian Florea greco Data 23 aprilie 2007 16:32:38
Problema Diamant Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
using namespace std;

#include <cstdio>
#include <cstring>

#define FIN "diamant.in"
#define FOUT "diamant.out"

#define MAX_N 32
#define MAX_M 32

int N, M, X, S;
unsigned int A[1<<18], B[1<<18];

int main()
{
	int i, j, k, p, d;
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);
	scanf("%d %d %d", &N, &M, &X);
	S = (N*M)*(N*M+1)/2;
	if (X < -S || X > S) {
		printf("0\n");
		return 0;
	}
	A[90000] = 1;
	for (p = i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j, ++p) {
			memset(B, 0, sizeof(B));
			for (d = i*j, k = -(S = p*(p+1)/2)+90000, S += 90000; k <= S; ++k) {
				B[k] = A[k-d]+A[k]+A[k+d];
				while (B[k] >= 1000000000)
					B[j] -= 1000000000;
			}
			memcpy(A, B, sizeof(A));
		}
	printf("%d\n", A[X+90000]%10000);
	return 0;
}