Pagini recente » Cod sursa (job #3364129) | Borderou de evaluare (job #3363925) | Cod sursa (job #3364091) | Cod sursa (job #3364396) | Cod sursa (job #3364010)
#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
*/