F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 4971. -- [Lydsy1708月赛]记忆中的背包

4971: [Lydsy1708月赛]记忆中的背包

Time Limit: 1 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 93  Solved: 25
[Submit][Status][Discuss]

Description

经过一天辛苦的工作,小Q进入了梦乡。他脑海中浮现出了刚进大学时学01背包的情景,那时还是大一萌新的小Q解
决了一道简单的01背包问题。这个问题是这样的:给定n个物品,每个物品的体积分别为v_1,v_2,...,v_n,请计算
从中选择一些物品(也可以不选),使得总体积恰好为w的方案数。因为答案可能非常大,你只需要输出答案对P取
模的结果。因为长期熬夜刷题,他只看到样例输入中的w和P,以及样例输出是k,看不清到底有几个物品,也看不
清每个物品的体积是多少。直到梦醒,小Q也没有看清n和v,请写一个程序,帮助小Q一起回忆曾经的样例输入。

Input

第一行包含一个正整数T(1<=T<=100),表示测试数据的组数。
接下来T行,每行3个整数w,P,k(50<=w<=20000,1<=P<=2^30,0<=k<=min(20000,P-1))
分别表示每组需要回忆的测试数据的相关参数。

Output

对于每组数据,第一行输出n(1<=n<=40)。
第二行输出n个正整数v_1,v_2,...,v_n(1<=v_i<=20000),分别表示每个物品的体积。
若有多组可行解,输出任意一组。输入数据保证对于每组数据至少存在一组可行解。

Sample Input

4
50 1013 4
50 3 1
80 5 1
100 1000000007 13

Sample Output

5
10 20 20 30 50
5
10 20 20 30 50
8
10 20 30 40 50 60 70 80
11
12 18 20 13 41 30 15 11 11 250 28

HINT

Source

本OJ付费获取

[Submit][Status][Discuss]

HOME Back