LightOJ 1231 Solution

Coin Change (I)

#include<bits/stdc++.h>

#define ll long long

#define mod 100000007

#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

vector<int>v(100), num(100);

ll dp[100][2000];

ll ways(int i, int x)

{

    if(x  == 0)

        return 1;

    if(x < 0 || i < 0)

        return 0;

    if(dp[i][x] != -1)

        return dp[i][x];

    ll cnt = 0;

    for(int j=0; j<=num[i]; j++)

        cnt = (cnt + ways(i-1, x - (j * v[i]))) % mod;

    return dp[i][x] = cnt;

}

int main()

{

    fastio

    int t, nm = 1;

    cin >> t;

    while(t--)

    {

        int n, k;

        cin >> n >> k;

        for(int i=0; i<n; i++)

            cin >> v[i];

        for(int i=0; i<n; i++)

            cin >> num[i];

        for(int i=0; i<=n; i++)

        {

            for(int j=0; j<=k; j++)

                dp[i][j] = -1;

        }

        cout << "Case " << nm++ << ": " << ways(n-1, k) << "\n";

    }

    return 0;

}