IOICamp 2024 題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
停機公告 今（2025/01/15）15:00～18:00 本站將進行系統維護，期間將無法評分提交的程式碼。
57 . 乘法背包問題
TopCoder
Tags
Description
蛋餅有一個厲害的背包，他稱之為「乘法背包」，乘法背包的運作方式是這樣的：每個放進去的物品都會有一個介在 $0 \sim D-1$ 的權重，其中 $D$ 是一個事先設定好的參數，當所有的物品放進背包裡後，他們綜合起來的權重就是這些物品的權重乘積除以 $D$ 的餘數。
雖然蛋餅的背包看似跟他的肚子一樣，看似可以裝下無限多的東西，但唯一不同的就是這個背包有一個穩定係數 $\mu$，只要裝進背包裡的物品總權重不是 $\mu$，那這個背包可能就會不穩定，放置太久就有可能會導致爆炸！
這天，蛋餅發現了 $N$ 個寶物，每個寶物都有它放進背包時的權重 $w_i$ 和價值 $v_i$，為了帶回價值總和最大的寶藏，蛋餅勢必得找出方法來讓寶藏的總權重為 $\mu$。同時，由於時間有限，蛋餅只能夠挑出 $K$ 個寶藏裝進背包裡；又因為某種私慾關係，他也不想拿少於 $K$ 個物品。因此，對於 $\mu = 0, 1, \ldots, D-1$，你能告訴蛋餅挑選恰 $K$ 個寶藏時，他能帶回去的最大價值總和嗎？
Input Format
輸入首行有三個整數 $N, K, D$，代表蛋餅發現的寶藏數量、蛋餅恰要拿的寶藏數量以及題敘內提到事先設定好的參數。
接下來 $N$ 行，第 $i$ 行兩個整數 $w_i, v_i$，代表第 $i$ 個寶物放進背包時的權重為 $w_i$、價值為 $v_i$。
- $1\leq K \leq N \leq 3\times 10^ 4$
- $1\leq D \leq 31$
- $0 \leq w_i < D$
- $1 \leq v_i \leq 4\times 10^ 4$
Output Format
輸出一行 $D$ 個整數 $ans_0, ans_1, \ldots, ans_{D-1}$ 以單一空格隔開，其中 $ans_i$ 代表 $\mu = i$ 時，蛋餅能帶回去的最大寶藏價值總和。
對於 $\mu=i$，如果無法挑選恰 $K$ 個物品使得總權重為 $i$，則 $ans_i = 0$。
Sample Input 1
3 7
3 10
4 8
2 1
0 9
Sample Output 1
Sample Input 2
1 6
2 18
6 4
3 10
5 3
1 14
5 9
7 20
4 15
2 12
Sample Output 2
Hints
建議注意實作常數，例如事先建好 $i\times j$ 模 $D$ 的表。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~10 | $N \leq 500$ | 20 |
| 3 | 11~16 | 無額外限制 | 80 |