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

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

  • ID: 284
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 背包
  • 动态规划
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

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

题目描述

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

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

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

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

输入格式

第一行一个整数 。

输出格式

输出一行,表示方案数。

样例

样例输入 1

3

样例输出 1

2

数据范围与提示

对于 的数据,满足

对于 的数据,满足

对于 的数据,满足

对于 的数据,满足

加强于原题


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