LightOJ 1232 Solution

Coin Change (II)

#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;

int n, k;

vector<int>c(150);

ll ways(int k)

{

    ll dp[k+1];

    for(int i=1; i<=k; i++)

        dp[i] = 0;

    dp[0] = 1;

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

    {

        for(int j=c[i]; j<=k; j++)

        {

            dp[j] += dp[j - c[i]];

            dp[j] %= mod;

        }

    }

    return dp[k];

}

int main()

{

    fastio

    int t, w = 1;

    cin >> t;

    while(t--)

    {

        cin >> n >> k;

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

            cin >> c[i];

        ll cnt = ways(k);

        cout << "Case " << w++ << ": " << cnt << "\n";

        c.clear();

    }

    return 0;

}