Light oj 1231 - Coin Change (I)(dp)

1231 - Coin Change (I)

PDF (English)

Statistics

Forum

Time Limit: 1 second(s)

Memory Limit: 32 MB

In a strange shop there are n types of coins of value A1, A2 ... An. C1, C2, ... Cn denote the number of coins of value A1, A2 ... An respectively. You have to find the number of ways you can make K using the coins.

For example, suppose there are three coins 1, 2, 5 and we can use coin 1 at most 3 times, coin 2 at most 2 times and coin 5 at most 1 time. Then if K = 5 the possible ways are:

1112

122

5

So, 5 can be made in 3 ways.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 50) and K (1 ≤ K ≤ 1000). The next line contains 2n integers, denoting A1, A2 ... An, C1, C2 ... Cn (1 ≤ Ai ≤ 100, 1 ≤ Ci ≤ 20). All Ai will be distinct.

Output

For each case, print the case number and the number of ways K can be made. Result can be large, so, print the result modulo 100000007.

Sample Input	Output for Sample Input
2 3 5 1 2 5 3 2 1 4 20 1 2 3 4 8 4 2 1	Case 1: 3 Case 2: 9

PROBLEM SETTER: JANE ALAM JAN

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define bug printf("hihi\n")

#define eps 1e-12

typedef long long ll;
using namespace std;
#define mod  100000007
#define N 1005

int n,a[N],num[N];
int dp[55][N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/ksh/Desktop/IN.txt","r",stdin);
#endif
    int i,j,t,ca=0;
    scanf("%d",&t);
    int all;
    while(t--)
    {
        scanf("%d%d",&n,&all);

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

        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;

        for(int i=1;i<=n;i++)
           for(int v=0;v<=all;v++)
           {
               int t=v/a[i];
               for(j=0;j<=t&&j<=num[i];j++)
                  dp[i][v]=(dp[i][v]+dp[i-1][v-j*a[i]])%mod;
           }

       printf("Case %d: %d\n",++ca,dp[n][all]);

    }
    return 0;
}