57 . 乘法背包問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

51.6% (33/64)

Tags

ioicamp ioicamp-2024

Description

蛋餅有一個厲害的背包，他稱之為「乘法背包」，乘法背包的運作方式是這樣的：每個放進去的物品都會有一個介在 0∼D−1 的權重，其中 D 是一個事先設定好的參數，當所有的物品放進背包裡後，他們綜合起來的權重就是這些物品的權重乘積除以 D 的餘數。

雖然蛋餅的背包看似跟他的肚子一樣，看似可以裝下無限多的東西，但唯一不同的就是這個背包有一個穩定係數 μ，只要裝進背包裡的物品總權重不是 μ，那這個背包可能就會不穩定，放置太久就有可能會導致爆炸！

這天，蛋餅發現了 N 個寶物，每個寶物都有它放進背包時的權重 wi 和價值 vi，為了帶回價值總和最大的寶藏，蛋餅勢必得找出方法來讓寶藏的總權重為 μ。同時，由於時間有限，蛋餅只能夠挑出 K 個寶藏裝進背包裡；又因為某種私慾關係，他也不想拿少於 K 個物品。因此，對於 μ=0,1,…,D−1，你能告訴蛋餅挑選恰 K 個寶藏時，他能帶回去的最大價值總和嗎？

Input Format

輸入首行有三個整數 N,K,D，代表蛋餅發現的寶藏數量、蛋餅恰要拿的寶藏數量以及題敘內提到事先設定好的參數。
接下來 N 行，第 i 行兩個整數 wi,vi，代表第 i 個寶物放進背包時的權重為 wi、價值為 vi。

  • 1≤K≤N≤3×104
  • 1≤D≤31
  • 0≤wi<D
  • 1≤vi≤4×104

Output Format

輸出一行 D 個整數 ans0,ans1,…,ansD−1 以單一空格隔開，其中 ansi 代表 μ=i 時，蛋餅能帶回去的最大寶藏價值總和。

對於 μ=i，如果無法挑選恰 K 個物品使得總權重為 i，則 ansi=0。

Sample Input 1

5 3 5
3 7
3 10
4 8
2 1
0 9

Sample Output 1

27 25 0 18 19

Sample Input 2

10 3 8
1 6
2 18
6 4
3 10
5 3
1 14
5 9
7 20
4 15
2 12

Sample Output 2

53 39 48 43 50 44 52 40

Hints

建議注意實作常數，例如事先建好 i×j 模 D 的表。

Problem Source

IOICamp 2024 Day6 pJ

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~10 N≤500 20
3 11~16 無額外限制 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2
1 3000 262144 65536 1 2
2 3000 262144 65536 2
3 3000 262144 65536 2
4 3000 262144 65536 2
5 3000 262144 65536 2
6 3000 262144 65536 2
7 3000 262144 65536 2
8 3000 262144 65536 2
9 3000 262144 65536 2
10 3000 262144 65536 2
11 3000 262144 65536 3
12 3000 262144 65536 3
13 3000 262144 65536 3
14 3000 262144 65536 3
15 3000 262144 65536 3
16 3000 262144 65536 3
Submit
Back to Top