Pagini recente » Cod sursa (job #3303589) | Cod sursa (job #3352224) | Cod sursa (job #3321131) | Cod sursa (job #3329448) | Cod sursa (job #3347587)
#include <iostream>
using namespace std;
#define mod 194767
int dpPoz[260][260 * (260 + 1) / 2];
int dpNeg[260][260 * (260 + 1) / 2];
bool vizPoz[260][65800];
bool vizNeg[260][65800];
int comb (int N, int S, int prev) {
if (N == 0) return 0;
long long maxp = 1LL * prev * N + N * (N + 1) / 2;
long long maxn = 1LL * prev * N - N * (N + 1) / 2;
if (S > 0) {
if (vizPoz[N][S]) {
return dpPoz[N][S];
} else {
if (maxp < S || maxn > S) return 0;
else if (maxp == S || maxn == S) return 1;
}
int retM = comb (N - 1, S + prev + 1, prev - 1);
int retP = comb (N - 1, S - prev - 1, prev + 1);
dpPoz[N][S] = ( (1LL * retM + retP) + dpPoz[N][S]) % mod;
vizPoz[N][S] = true;
return dpPoz[N][S];
} else {
if (vizNeg[N][-S]) {
return dpNeg[N][-S];
} else {
if (maxn > S || maxp < S) return 0;
else if (maxn == S || maxp == S) return 1;
}
int retM = comb (N - 1, S + prev + 1, prev - 1);
int retP = comb (N - 1, S - prev - 1, prev + 1);
dpNeg[N][-S] += ( (1LL * retM + retP) + dpNeg[N][-S]) % mod;
vizNeg[N][-S] = true;
return dpNeg[N][-S];
}
}
int main() {
freopen("1-sir.in", "r", stdin);
freopen("1-sir.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N, S;
cin >> N >> S;
cout << comb(N - 1, S, 0);
return 0;
}