Cod sursa(job #14262)

Utilizator victorsbVictor Rusu victorsb Data 8 februarie 2007 17:00:02
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <string.h>

#define Nmax 260

const int modul = 194767;
int n, s;
int d1[Nmax * Nmax], d2[Nmax * Nmax];

void citire()
{
    scanf("%d %d\n", &n, &s);
}

inline int mod(int x)
{
    if (x >= 0)
        return x;
    return -x;
}

void solve()
{
    int i, j, smax = n * (n-1) / 2;
    d1[0] = 1;
    for (i=1; i<n; ++i)
    {
        memset(d2, 0, sizeof(d2));
        for (j=-smax; j<0; ++j)
        {
            if (j+i >= 0)
            {
                d2[j+i] += d1[-j];
                if (d2[j+i] >= modul)
                    d2[j+i] -= modul;
            }
            if (j-i >= 0)
            {
                d2[j-i] += d1[-j];
                if (d2[j-i] >= modul)
                    d2[j-i] -= modul;
            }
        }
        for (j=0; j<=smax; ++j)
        {
            if (j+i >= 0)
            {
                d2[j+i] += d1[j];
                if (d2[j+i] >= modul)
                    d2[j+i] -= modul;
            }
            if (j-i >= 0)
            {
                d2[j-i] += d1[j];
                if (d2[j-i] >= modul)
                    d2[j-i] -= modul;
            }
        }
        memcpy(d1, d2, sizeof(d1));
    }
    printf("%d\n", d2[s]);
}

int main()
{
    freopen("1-sir.in", "r", stdin);
    freopen("1-sir.out", "w", stdout);
    citire();
    solve();
    return 0;
}