Cod sursa(job #911133)

Utilizator ELHoriaHoria Cretescu ELHoria Data 11 martie 2013 12:53:33
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <string>
#include <cstring>
#include <map>

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;
}