#P4971. [Lydsy1708月赛]记忆中的背包
[Lydsy1708月赛]记忆中的背包
[Lydsy 2017 年 8 月月赛] 记忆中的背包
题目描述
小 Q 在梦里回想起大学初次做的 0–1 背包题。给定 件物品,体积为 。每件物品可选一次或不选,体积相同的不同物品也可分别选择。要统计总体积恰好为 的选取方案数对 取模的结果。
梦中他只看清了 和样例输出 。请恢复任意一组能得到该输出的物品体积。
输入格式
第一行一个正整数 ,满足 。
接下来 行,每行三个整数 ,满足 、、。
输出格式
对每组数据输出两行。第一行输出整数 ,满足 。第二行输出 个正整数 ,满足 。所构造的物品中,总体积恰为 的子集数对 取模后必须为 。
每组数据保证至少有一个可行解,输出任意一个即可。
样例
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
相关
在下列比赛中: