Cod sursa(job #3364010)

Utilizator alex.iovita.23@gmail.comIovita Alexandru [email protected] Data 26 august 2026 00:07:04
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("1-sir.in");
ofstream fout("1-sir.out");

int n , s;
const int MOD = 194767;

signed main(){
    fin >> n >> s;
    int smax = n * (n - 1) / 2;
    int dif = smax - s;
    if(dif < 0 || dif % 2 != 0){
        fout << 0;
        return 0;
    }
    int target = dif / 2;
    vector<int> dp(target + 1 , 0); // dp[i] = numarul de moduri de obtine suma i
    dp[0] = 1; // avem un mod pt a obtine suma 0
    for(int i = 1 ; i < n ; i++){
        //parcurgem de la dreapta la stanga ca sa nu refolosim acelasi element i
        for(int j = target ; j >= i ; j--){
            dp[j] = (dp[j] + dp[j - i]) % MOD;
        }
    }
    fout << dp[target];
}
/*
EXPLICATIE:
s1 = 0
s2 = s1 + x1 = 0 + x1 = x1
s3 = s2 + x2 = x1 + x2
...
sn = s(n-1) + xn = x1 + x2 + ... + xn , unde xn apartine {-1 , 1}
Dar stim ca S = s1 + s2 + ... + sn deci rezulta ca S = x1 + x1 + x2 + ... x1 + x2 + ... + xn =>
=> S = (n - 1) * x1 +   (n - 2) * x2 + ... + xn-1
Fie xi = (2 * yi - 1) , unde yi apartine {0 , 1} =>
=> S = (n - 1) * (2 * y1 - 1) + (n - 2) * (2 * y2 - 1) + ... + 2 * yn-1 - 1 =>
=> S = SUM(de la i = 1 pana la n - 1) 2 * yi * i - (n - 1) * n / 2 =>
=> 2 * SUM(de la i = 1 pana la n - 1) yi * i = S + n * (n - 1) / 2 =>
=> SUM(de la i = 1 pana la n - 1) yi * i = (S + (n - 1) * n / 2) / 2
deci target ul nostru este (S + n * (n - 1) / 2) / 2
adica SUM(de la i = 1 pana la n - 1) yi * i ne ajuta sa aflam numarul de moduri de a alege o sumultime
din multimea {1 , 2, .. , n-1} a.i. suma elementeloe alese sa fie egala cu target
Daca nu s a inteles de ce SUM(de la i = 1 pana la n - 1) yi * i este special deci stim ca yi poate fi 0 sau 1 nu?
atunci alea alese inseamna ca yi este 1 si alea care nu au fost alese inseamna ca yi = 0 deci pt xi inseamna ca
pt yi = 1 atunci xi = 1 si pt yi = 0 xi = -1
p.s:foarte tare problema dar totusi greu de ajuns pana aici
*/