Cod sursa(job #2638955)

Utilizator loraclorac lorac lorac Data 30 iulie 2020 18:11:11
Problema Cowfood Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("cowfood.in");
ofstream out("cowfood.out");
typedef unsigned long long int si;
const int mod=3210121;
const int lim=(1<<20)+3;
si maxx[2][32][184780];
si v[22][32];
int cnt;
vector<int> nr[22];
int poz[lim];
int put[10002];
int f[33];
int power(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=(1LL*ans*a)%mod;
        a=(1LL*a*a)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    int k,s,n;
    in>>k>>s>>n;
    for(int i=0;i<n;++i)
    for(int j=1;j<=k;++j)
        in>>v[i][j];
    put[0]=1;
    int fact=1;
    for(int i=1;i<=k;++i)
        fact=(1LL*fact*i)%mod;
    fact=power(fact,mod-2);
    for(int i=1;i<=s;++i)
    {
        put[i]=fact;
        for(int j=i+1;j<=i+k;++j)
            put[i]=(1LL*put[i]*j)%mod;
    }
    int supp=(1<<n);
    for(int i=1;i<supp;++i)
        nr[__builtin_popcount(i)].push_back(i);
    for(int i=1;i<=k;++i)
        maxx[0][i][1]=0;
    poz[0]=1;
    int ans=(put[s]-(s*k+1)%mod+mod)%mod;
    for(int cb=1;cb<=n;++cb)
    {
        cnt=0;
        int now=cb%2,last=1-cb%2;
        for(auto t:nr[cb])
        {
            poz[t]=++cnt;
            int cr=t&-t,r=t&-t,b=0;
            while(cr>1) cr>>=1,++b;
            int apel=poz[t-r],sum=s;
            for(int i=1;i<=k;++i)
            {
                maxx[now][i][cnt]=max(maxx[last][i][apel],v[b][i]);
                sum-=(int)maxx[now][i][cnt];
            }
            if(sum<0) continue;
            if(now==1) ans=(ans-put[sum]+mod)%mod;
            else ans=(ans+put[sum])%mod;
        }
    }
    for(int i=1;i<=k;++i)
        f[i]=s+1;
    for(int i=0;i<n;++i)
    {
        cnt=0;
        for(int j=1;j<=k;++j)
        if(v[i][j]>0) cnt++;
        if(cnt==1) for(int j=1;j<=k;++j)
        if(v[i][j]>0) f[j]=min(f[j],(int)v[i][j]);
        if(cnt==0) {out<<0<<'\n';return 0;}
    }
    for(int i=1;i<=k;++i)
        ans=(ans+(s-f[i]+1))%mod;
    out<<ans<<'\n';
    return 0;
}