跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0278. #6089. 小 Y 的背包计数问题

    ID: 284 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>背包动态规划难度待定难度共享题库LibreOJ中文题面题目来源题面语言

#6089. 小 Y 的背包计数问题

题目描述

小 Y 有一个大小为 的背包,并且小 有 种物品。

对于第 种物品,共有 个可以使用,并且对于每一个 物品,体积均为 。

求小 把该背包装满的方案数为多少,答案对于 取模。

定义两种不同的方案为:当且仅当至少存在一种物品的使用数量不同。

输入格式

第一行一个整数 。

输出格式

输出一行,表示方案数。

样例

样例输入 1

3

样例输出 1

2

数据范围与提示

对于 的数据,满足

对于 的数据,满足

对于 的数据,满足

对于 的数据,满足

加强于原题


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 175 题。保留原作者与原赛事署名。