Pagini recente » Cod sursa (job #1344002) | Cod sursa (job #2704545) | Cod sursa (job #1104767) | Cod sursa (job #3266591) | Cod sursa (job #7043)
Cod sursa(job #7043)
#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;
}