Cod sursa(job #1538839)

Utilizator algebristulFilip Berila algebristul Data 29 noiembrie 2015 21:03:23
Problema Cowfood Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

#define FILEIN "cowfood.in"
#define FILEOUT "cowfood.out"

using namespace std;

int k, S, n;
int a[20][31];
int D[1<<20][31];
int values[31];
bool Zero = false;
long long sums[10005];
const int MOD = 3210121;

long long explog(long long x, int pow) {
    long long t = x;
    long long sol = 1;

    while (pow) {
        if (pow & 1) {
            sol = sol * t;
            sol %= MOD;
        }

        t = t * t;
        t %= MOD;
        pow >>= 1;
    }

    return sol;
}

inline int lsb(int x) {
    return x & (-x);
}

inline int popcnt(int x) {
    int y = 0;
    while (x) {
        y++;
        x = x ^ lsb(x);
    }
    return y;
}

void pre() {
    // sums[i] = combinari de i + k - 1 luate cate k - 1
    // = (i+k - 1)! / (i)! * (k - 1)!

    long long kfact = 1;
    for (int i = 2; i < k; i++) {
        kfact *= i;
        kfact %= MOD;
    }

    // invmod
    kfact = explog(kfact, MOD - 2);

    long long fact_upper = 1;
    long long fact_lower = 1;

    for (int i = 2; i < k - 1; i++) {
        fact_upper *= i;
        fact_upper %= MOD;
    }

    for (int i = 0; i <= S; i++) {
        fact_upper *= (k + i - 1);
        fact_upper %= MOD;
        fact_lower *= (i > 0) ? i : 1;
        fact_lower %= MOD;

        sums[i] = kfact;
        sums[i] *= explog(fact_lower, MOD - 2);
        sums[i] %= MOD;
        sums[i] *= fact_upper;
        sums[i] %= MOD;
    }

    for (int i = 1; i <= S; i++) {
        sums[i] += sums[i-1];
        if (sums[i] >= MOD)
            sums[i] -= MOD;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            D[1<<i][j] = a[i][j];
        }
    }

    for (int m = 0; m < (1 << n); m++) {
        for (int j = 1; j <= k; j++) {
            D[m][j] = max(D[m ^ lsb(m)][j], D[lsb(m)][j]);
        }
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d %d", &k, &S, &n);
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    pre();

    long long ans = 0;
    for (int m = 0; m < (1<<n); m++) {
        int sign = 1;
        if (popcnt(m) % 2)
            sign = -1;

        long long sum = 0;
        for (int j = 1; j <= k; j++) {
            sum += D[m][j];
        }

        if (sum > S)
            continue;

        ans += 1LL * sign * sums[S - sum];
        if (ans < 0)
            ans += MOD;
        if (ans >= MOD)
            ans -= MOD;
    }

    ans -= 1LL * S * k + 1LL;
    if (ans < 0)
        ans += MOD;

    printf("%lld\n", ans);

    return 0;
}