三輪（背包）

題目描述 

小k有一個三輪，它最多可以裝105大小的東西

小k有n種商品，他要準備出攤了

每種商品體積為vi，都有105件

輸出湊成1~m的體積的總方案數

輸出可能會很大，請對大質數19260817取模

輸入描述:

第一行兩個整數n,m，

接下來n行，每行一個數代表vi

輸出描述:

一個數ans表示總方案數

示例1

輸入

複制

2 8

1

3

輸出

複制

17

說明

從1~m體積的方案數分别為：

1

1

2

2

2

3

3

3

備注:

不要忘記取模！！！

n,m,vi <= 50000

思路：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn =5e4+100;
const int mod = 19260817;
int a[maxn];
int sum[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);

    ll sum_1=0;
    sum[0]=1;
    for(int i=1; i<=n; i++)
    {
        for(int v=a[i]; v<=m; v++)
        {
            sum[v]=(sum[v-a[i]]+sum[v])%mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        //cout<<sum[i]<<endl;
        sum_1=(sum_1+sum[i])%mod;
    }
    printf("%lld\n",sum_1);
    return 0;
}