Pagini recente » Cod sursa (job #3341823) | Cod sursa (job #3316377) | Cod sursa (job #3332945) | Cod sursa (job #3330738) | Cod sursa (job #3347594)
#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) {
cout << N << ' ' << S << ' ' << prev << '\n';
if (N == 0) return (S == 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) % 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) % 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;
}