Cod sursa(job #3220485)

Utilizator ezluciPirtac Eduard ezluci Data 3 aprilie 2024 19:45:35
Problema 1-sir Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "1-sir";
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int MOD = 194767;

map<tuple<int,int,int>, int> dp;
int solvedp(int n, int s, int last)
{
   if (dp.count(make_tuple(n, s, last)))  return dp[make_tuple(n, s, last)];
   if (n == 1) return 0;

   return dp[make_tuple(n, s, last)] = (solvedp(n-1, s-last, last-1) + solvedp(n-1, s-last, last+1)) % MOD;
}

int main()
{
   int n, s;   cin >> n >> s;
   if (abs(s) > n*(n-1)/2) cout << 0,  exit(0);

   dp[make_tuple(1, 0, 0)] = 1;
   int ans = 0;
   for (int last = -n+1; last <= n+1; last += 2)
   {
      ans += solvedp(n, s, last);
      if (ans >= MOD)   ans -= MOD;
   }

   cout << ans;
}