Pagini recente » Cod sursa (job #1503954) | Cod sursa (job #2468512) | Cod sursa (job #429708) | Cod sursa (job #1892915) | Cod sursa (job #1734384)
#include <cstdio>
#define MAXS 10000
#define MAXK 30
#define MOD 3210121
using namespace std;
struct experiment{
int cant[MAXK+4];
} v[MAXK+3], aux[MAXK+3], expe;
int dp[MAXK+8][MAXS+8], n, k, s, sol;
inline int maxim(int a, int b){
if(a>b)
return a;
return b;
}
void bkt(int niv, int cate){
if(niv>=n){
int sum=0;
for(int i=0; i<k; i++)
sum+=expe.cant[i];
if(sum<=s && cate>0){
if(cate&1){
sol+=dp[k+1][s-sum];
if(sol>=MOD)
sol-=MOD;
} else{
sol-=dp[k+1][s-sum];
if(sol<0)
sol+=MOD;
}
}
return;
}
bkt(niv+1, cate);
for(int i=0; i<k; i++){
aux[niv].cant[i]=expe.cant[i];
expe.cant[i]=maxim(expe.cant[i], v[niv].cant[i]);
}
bkt(niv+1, cate+1);
for(int i=0; i<k; i++)
expe.cant[i]=aux[niv].cant[i];
}
int main()
{
FILE *fin, *fout;
int i, j;
fin=fopen("cowfood.in", "r");
fscanf(fin, "%d%d%d", &k, &s, &n);
for(i=0; i<n; i++)
for(j=0; j<k; j++)
fscanf(fin, "%d", &v[i].cant[j]);
fclose(fin);
for(j=0; j<=MAXK+1; j++)
dp[j][0]=1;
for(i=1; i<=MAXS+1; i++){
for(j=0; j<=MAXK+1; j++){
if (j==0 || j==1)
dp[j][i]=1;
else
dp[j][i]=(dp[j-1][i]+dp[j][i-1])%MOD;
}
}
bkt(0, 0);
fout=fopen("cowfood.out", "w");
fprintf(fout, "%d", ((dp[k+1][s]-sol-s*k-1)%MOD+MOD)%MOD);
fclose(fout);
return 0;
}