Cod sursa(job #838175)

Utilizator elfusFlorin Chirica elfus Data 19 decembrie 2012 00:54:35
Problema 1-sir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#define MOD 194767
 
inline void baga(int &A, int B)
{
    A += B;
    if (A >= MOD)
        A = A - MOD;
}
 
inline int ab(int X)
{
    if (X > 0)
        return X;
    return X * (-1);
}
 
int dp[2][90000];
 
int main()
{
    int i, j, N, S, lim;
     
    freopen("1-sir.in", "r", stdin);
    freopen("1-sir.out", "w", stdout);
     
    scanf("%d%d", &N, &S);
    S = ab(S);
	lim = N * (N - 1) / 2;
    if (lim < S)
    {
        printf("0");
        return 0;
    }
     
    int sol = 0;
     
    dp[1][0] = 1;
    for (i = 1; i <= N; i ++)
	{
        for (j = 0; j <= lim; j ++)
        {
            if (j + i <= lim)
                baga(dp[(i + 1) & 1][j + i], dp[i & 1][j]);
            baga(dp[(i + 1) & 1][ab(j - i)], dp[i & 1][j]);
		}
		
		if (i == N)
			sol = dp[i & 1][S];
		for (j = 0; j <= lim; j ++)
			dp[i & 1][j] = 0;
	}  
    printf("%d", (long long)sol * 97384 % MOD);
    return 0;
}