#P4971. [Lydsy1708月赛]记忆中的背包

    ID: 4071 传统题 1000ms 256MiB 尝试: 197 已通过: 71 难度: 7 上传者: 标签>难度分类提高+/省选-构造与建模序列构造动态规划完全背包枚举与搜索路径恢复组合数学Pascal 递推加法原理CF2300本OJ付费获取

[Lydsy1708月赛]记忆中的背包

[Lydsy 2017 年 8 月月赛] 记忆中的背包

题目描述

小 Q 在梦里回想起大学初次做的 0–1 背包题。给定 nn 件物品,体积为 v1,v2,…,vnv_1,v_2,\ldots,v_n。每件物品可选一次或不选,体积相同的不同物品也可分别选择。要统计总体积恰好为 ww 的选取方案数对 PP 取模的结果。

梦中他只看清了 w,Pw,P 和样例输出 kk。请恢复任意一组能得到该输出的物品体积。

输入格式

第一行一个正整数 TT,满足 1≤T≤1001\le T\le100。

接下来 TT 行,每行三个整数 w,P,kw,P,k,满足 50≤w≤2000050\le w\le20000、1≤P≤2301\le P\le2^{30}、0≤k≤min⁡(20000,P−1)0\le k\le\min(20000,P-1)。

输出格式

对每组数据输出两行。第一行输出整数 nn,满足 1≤n≤401\le n\le40。第二行输出 nn 个正整数 v1,v2,…,vnv_1,v_2,\ldots,v_n,满足 1≤vi≤200001\le v_i\le20000。所构造的物品中,总体积恰为 ww 的子集数对 PP 取模后必须为 kk。

每组数据保证至少有一个可行解,输出任意一个即可。

样例

4
50 1013 4
50 3 1
80 5 1
100 1000000007 13
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