Pagini recente » Istoria paginii runda/ioi2014./clasament | Cod sursa (job #2562434) | Cod sursa (job #1095495) | Cod sursa (job #1088246) | Cod sursa (job #911135)
Cod sursa(job #911135)
#include <fstream>
#include <string>
#include <cstring>
#include <map>
#include <cstdlib>
using namespace std;
ifstream cin("1-sir.in");
ofstream cout("1-sir.out");
const int mod = 194767, SMAX = 1<<13;
inline void getMod(int &val){ val -= val < mod ? 0 : mod;}
int N;
long long S;
int dp[2][256][SMAX<<1];
int s1;
int v[32];
void go(int i,int val,int sum) {
if(i == N + 1) {
if(sum == S) {
for(int k = 1;k <= N;k++) cout<<v[k]<<" ";cout<<"\n";
s1++;
}
}
else {
v[i] = val - 1;
go(i + 1,val - 1,sum + val - 1);
v[i] = val + 1;
go(i + 1,val + 1,sum + val + 1);
}
}
map< pair<int,long long>,int > h;
int memo(pair<int,long long> s) {
map< pair<int,long long>,int >::iterator it = h.find(s);
if(it != h.end()) return it->second;
h[s] = 0;
int &ret = h[s];
int i = s.first & 255;
int j = (s.first>>10) & 1023;
// cout<<i<<" "<<j<<" "<<s.second<<"\n";
int rj = j - N;
if(i == N - 1) {
return ret = (s.second == S);
}
pair<int,long long> urm;
urm.first = (i + 1) + ((j - 1)<<10);
urm.second = s.second + rj - 1;
ret += memo(urm);
urm.first = (i + 1) + ((j + 1)<<10);
urm.second = s.second + rj + 1;
ret += memo(urm);
getMod(ret);
return ret;
}
int solve() {
if(abs(S) > N*(N - 1)/2) return 0;
return memo(make_pair(N<<10,0));
}
int main()
{
cin>>N>>S;
cout<<solve()<<"\n";
return 0;
}