Cod sursa(job #3353477)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 7 mai 2026 17:02:57
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <cassert>
#include <algorithm>
#include <vector>

template<class T> using vec = std::vector<T>;

constexpr int MOD = 194767;
struct ZP {
  int x;
  constexpr ZP( int x = 0 ): x(x % MOD) {}
  explicit operator int() const { return x; }

  ZP operator += ( const ZP& that ) { x += that.x; if( x >= MOD ) x -= MOD; return *this; }
  ZP operator -= ( const ZP& that ) { x += MOD - that.x; if( x >= MOD ) x -= MOD; return *this; }
  ZP operator + ( const ZP& that ) const { return ZP(*this) += that; }
  ZP operator - ( const ZP& that ) const { return ZP(*this) -= that; }
};

template<class T>
struct Zvec { 
  int lo, hi;
  vec<T> v;
  Zvec( int lo, int hi, const T& x ): lo(lo), hi(hi), v(hi - lo + 1, x) {}
  T& operator []( int x ) { return v[x - lo]; }
  const T& operator []( int x ) const { return v[x - lo]; }
};

int main() {
  std::ifstream fin("1-sir.in");
  std::ofstream fout("1-sir.out");

  int n, S;
  fin >> n >> S;

  Zvec<ZP> sums(0, 0, 1);
  for( int i = 1; i < n; i++ ){
    int D = n - i;
    Zvec<ZP> next(sums.lo - D, sums.hi + D, 0);
    for( int x = sums.lo; x <= sums.hi; x++ ){
      next[x + D] += sums[x];
      next[x - D] += sums[x];
    }
    sums = next;
  }

  if( sums.lo <= S && S <= sums.hi )
    fout << int(sums[S]) << std::endl;
  else
    fout << "0\n";
  
  return 0;
}