題干：

鏈接：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 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 157F】三轮（dp，分治fft）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。