题干:
链接:https://ac.nowcoder.com/acm/contest/157/F
来源:牛客网
小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
解题报告:
注意这题不能直接取模,会TLE,要if判断,就能过了。。(数据水了,这不是正解)正解是分治fft???
AC代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
const ll mod = 19260817;
ll dp[MAX];
ll val[MAX];
int main()
{
int n,m;
cin>>n>>m;
dp[0]=1;
for(int i = 1; i<=n; i++) scanf("%lld",val+i);
for(int i = 1; i<=n; i++) {
for(int j = val[i]; j<=m; j++) {
dp[j] = (dp[j] + dp[j-val[i]]);
if(dp[j] >= mod) dp[j] -= mod;
}
}
ll ans = 0;
for(int i = 1; i<=m; i++) ans = (ans + dp[i]) % mod;
printf("%lld\n",ans);
return 0 ;
}