Cod sursa(job #1303085)

Utilizator smaraldaSmaranda Dinu smaralda Data 27 decembrie 2014 16:41:47
Problema Cowfood Scor 46
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

const int MOD = 3210121, NMAX = 21, KMAX = 31, SMAX = 10005;
int s, k, a[NMAX][KMAX], comb[SMAX + KMAX][KMAX], sumComb[SMAX + KMAX], esuat[KMAX], lim[KMAX];

inline bool testBit (int x, int bit) {
    return x & (1 << bit);
}

void genComb (int limi, int limj) {
    int i, j;

    for(i = 0; i <= limi; ++ i) {
        comb[i][0] = 1;
        for(j = 1; j <= i && j <= limj; ++ j)
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
    }

    for(i = 1; i <= s; ++ i)
        sumComb[i] = (sumComb[i - 1] + comb[i + k - 1][k - 1]) % MOD;
}

int main() {
    freopen("cowfood.in", "r", stdin);
    freopen("cowfood.out", "w", stdout);
    int card, cnt, subset, newSum, total, naspa, i, j, n;

    scanf("%d%d%d", &k, &s, &n);
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= k; ++ j)
            scanf("%d", &a[i][j]);

    genComb(s + k - 1, k - 1);

    total = sumComb[s] - k * s;

    naspa = 0;
    for(subset = 1; subset < (1 << n); ++ subset) {
        memset(lim, 0, sizeof(lim));

        cnt = 0;
        for(i = 0; i < n; ++ i)
            if(testBit(subset, i)) {
                ++ cnt;

                for(j = 1; j <= k; ++ j)
                    lim[j] = max(lim[j], a[i + 1][j]);
            }

//        fprintf(stderr, "\n%d %d\n", subset, cnt);
  //      for(i = 1; i <= k; ++ i)
    //        fprintf(stderr, "%d ", lim[i]);
 
        newSum = s;
        for(i = 1; i <= k; ++ i)
            newSum -= lim[i];
      
        card = sumComb[newSum];
        if(newSum >= 0)
            card = (card + 1) % MOD;

       // fprintf(stderr, "\nsum = %d, card = %d\n", newSum, card);

        if(cnt % 2 == 1)
            naspa = (naspa + card) % MOD;
        else
            naspa = (naspa - card) % MOD;
    }

    printf("%d\n", (total - naspa) % MOD);
    return 0;
}