Cod sursa(job #3347583)

Utilizator G_b_yZamfirache Gabriel G_b_y Data 17 martie 2026 12:25:38
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#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) {
    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;
}