Cod sursa(job #227547)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 4 decembrie 2008 21:11:54
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>
#include <math.h>

#define MAXN 70000

long lim, cur, n, s, din[2][MAXN], i, j;

long modul(long x) { 
	if (x < 0) {
		return -x;
	}
	return x;
}

int main() {
	freopen("1-sir.in", "r", stdin);
	freopen("1-sir.out", "w", stdout);
	scanf("%ld %ld", &n, &s);
	lim = n * (n + 1) / 2;
	din[1][0] = 1;
	if (modul(s) > lim) {
		printf("0\n");
		return 0;
	}
	for (i = 2, cur = 0; i <= n; ++i) {
		for (j = 0; j <= lim; ++j) {
			din[cur][j] = (din[1 - cur][modul(j - (i - 1))] + din[1 - cur][modul(j + (i - 1))]) % 194767;
		}
		cur = 1 - cur;
	}
	printf("%ld\n", din[n % 2][modul(s)]);
	return 0;
}