Cod sursa(job #2429349)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 9 iunie 2019 11:41:42
Problema Cowfood Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

const int MOD = 3210121;
const int NMAX = 20;
const int KMAX = 30;
const int SMAX = 1e4;

int dp[SMAX + 1];
int mix[NMAX][KMAX];
int choose[SMAX + KMAX + 1][KMAX + 1];

int add(int a, int b) {
  a += b;
  while (a >= MOD) a -= MOD;
  while (a < 0) a += MOD;
  return a;
}

int mul(int a, int b) {
  return 1LL *a * b % MOD;  
}

void calcChoose(int n, int k) {
  for (int i = 0; i <= n; ++i) {
    choose[i][0] = 1;
    for (int j = 1, lim = min(i, k); j <= lim; ++j) {
      choose[i][j] = add(choose[i - 1][j - 1], choose[i - 1][j]); 
      // nici sa fac triunghiu lui pascal nu-s in stare si ma mir ca iau aproape 0
    }
  }
}

int pinex(int pos, int n, int k, int s, int sign, vector<int> curr) {
  if (pos == n) {
    int remaining = s, non_zero = 0;
    for (int &x : curr) {
      remaining -= x;
      non_zero += x != 0;
    }
    if (non_zero >= 2) return sign * dp[remaining];
    if (non_zero == 1) return sign * add(dp[remaining], -remaining);
    if (non_zero == 0) return sign * add(add(dp[remaining], -k * remaining), -1);
    assert(false);
  }
  int ret = pinex(pos + 1, n, k, s, sign, curr);
  int remaining = s;
  for (int i = 0; i < k; ++i) {
    curr[i] = max(curr[i], mix[pos][i]);
    remaining -= curr[i];
  }
  if (remaining < 0) return ret;
  ret = add(ret, pinex(pos + 1, n, k, s, sign * -1, curr));
  return ret;
}

int main() {
  freopen("cowfood.in", "r", stdin);
  freopen("cowfood.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);

  int k, s, n; cin >> k >> s >> n;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < k; ++j) {
      cin >> mix[i][j];
    }
  }
  calcChoose(s + k, k);
  // dp[i] = nr de moduri de a pune maxim i obiecte identice in k cutii distincte
  dp[0] = 1;
  for (int i = 1; i <= s; ++i) {
    dp[i] = add(dp[i - 1], choose[i + k - 1][k - 1]);
  }
  vector<int> curr(k);
  cout << pinex(0, n, k, s, 1, curr) << endl;
  
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}