組合布丁
https://tioj.ck.tp.edu.tw/problems/1628
Description
記得在快樂暑假營開始前，你曾經說過：「只要我有一次比賽沒有破台，就要請全快樂營的人吃布丁。」
好吧，蚯蚓太威了，你終究是沒有破台。
根據小道消息，你得知了這次的快樂暑假營總共有 $n$ 個人報名，
但是實際上會出席的只有 $k$ 個人，因此你只要請 $k$ 個人吃布丁就好。
而報名的第 $i$ 個人只會願意吃 $t_i$ 口味的布丁(用一個 int 範圍內的整數表示)。
假設你不確定究竟誰會出席，那有幾種不同的布丁組合可能會出現在你的採買清單上 ?
喔對了，因為答案可能太大了，所以你決定只要知道答案除以 $M$ 的餘數就好。
輸入包含多筆測資
$$
1 \leq n, k \leq 5000, 1 \leq M < 2^{31}
$$
Solution
兩種布丁組合不同，若且唯若某一種布丁的數量不同
因此我們枚舉每個布丁的數量去做計數背包就好了
可以用前綴和甚至FFT加速(?)不過FFT應該不會比較快www
AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
int t[5025], n, k, M;
long long dp[5025];
void go(int maxcnt) {
for(int i = k; i >= 0; i--) {
long long sum = 0;
for(int j = 0; j <= i && j <= maxcnt; j++) {
sum = (sum + dp[i-j])%M;
}
dp[i] = sum;
}
}
signed main() {
while(cin >> n >> k >> M) {
dp[0] = 1;
for(int i = 1; i <= k; i++) dp[i] = 0;
for(int i = 0; i < n; i++) cin >> t[i];
sort(t,t+n);
for(int i = 0, j; i < n; i = j) {
for(j = i; j < n; j++) if(t[i] != t[j]) break;
go(j-i);
}
cout << dp[k] << '\n';
}
}
|