Cod sursa(job #7043)

Utilizator astronomyAirinei Adrian astronomy Data 21 ianuarie 2007 12:05:30
Problema 1-sir Scor 30
Compilator c Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 1.61 kb
#include <stdio.h>

#define MOD 194767
#define MAXN 128
#define MAXS (127*128+128)

const int VAL = 127*64;

int N, S, V;
int A[2][MAXN][MAXS];

int cnt, x[32];

void bkt(int k)
{
    int s, i, t;

    if(k == N+1)
    {
        for(s = t = 0, i = 2; i <= N; i++)
        {
            t = (x[i] == 1 ? t+1 : t-1);
            s += t;
        }
        if(s == S)
            cnt++;
    }
    else
        x[k] = 0, bkt(k+1), x[k] = 1, bkt(k+1);
}

int solve(void)
{
    int n, p, s, t, u = 0, v = 1, res = 0;

    A[u][0][0+VAL] = 1;

    for(n = 2; n <= N; n++)
    {
        for(p = 0; p <= n; p++)
         for(s = (-1)*V; s <= V; s++)
         {
            A[v][p][s+VAL] = 0;
            if( (t = (s-(n-1-2*p)+VAL)) < MAXS )
            {

                A[v][p][s+VAL] = A[u][p][t];
                if(p > 0)
                    A[v][p][s+VAL] += A[u][p-1][t];
                if(A[v][p][s+VAL] >= MOD)
                    A[v][p][s+VAL] -= MOD;
            }
         }
        u ^= 1, v ^= 1;
    }

    for(p = 0; p <= N; p++)
    {
        res += A[u][p][S+VAL];
        if(res >= MOD)
            res -= MOD;
    }

    return res;

}

int main(void)
{
    freopen("1-sir.in", "rt", stdin);
    freopen("1-sir.out", "wt", stdout);

    int i, j;

    scanf("%d %d\n", &N, &S);

    V = (N-1)*N/2;

    if(S < (-1)*V || S > V)
    {
        printf("0\n");
        return 0;
    }

    if(N <= 20)
    {
        bkt(2);
        printf("%d\n", cnt % MOD);
    }
    else
        printf("%d\n", solve());

    return 0;
}