活动(act)
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
超市里,有 种物品,第 种物品的重量为 ,且每种物品都有无限多个。有一天,超市举办了一个活动。活动的规则是:首先你从盒子里抽取一个数字 ,你有一个空篮子,初始时篮子内物品总重量为 。你每次可以将一个物品放入篮子,但假设当前篮子内物品总重量为 ,则只能选择重量 的物品放进篮子。你可以按照规则放多次,但不能把已经在篮子里的物品取出篮子。如果你可以按照规则,使得篮子内物品的总重量刚好为 ,则超市就赠送你一个小礼品。[丛雨]发现了这个活动的一个必胜策略,她参加了很多次活动,导致超市面临亏损。于是在丛雨打算再次参与活动时,超市老板对丛雨提出挑战,如果丛雨可以不使用第 种物品的前提下,仍然使篮子内物品的总重量刚好为 ,则超市老板就赠送丛雨一份大礼品,否则丛雨将再也不许参加活动。丛雨欣然接受,她只是觉得无聊。于是她打算考考你,在不使用第 种物品的前提下,她可以有多少种合法的放物品方案,使得篮子内物品的总重量刚好为 ?两种方案不同当且仅当丛雨在两种方案中篮子内物品的数量不同,或者两种方案中第 次放到篮子的物品种类不同。由于方案数可能很大,她只需要你输出方案数除以 的余数就可以啦。
输入格式(act.in)
一行三个正整数 ,以空格相隔。
输出格式(act.out)
一行,一个整数,表示方案数除以 的余数。
输入样例A
5 7 3
输出样例A
3
输入样例B
12345 4321 24
输出样例B
795333476
数据范围
对于 的数据,满足 。 对于 的数据,满足 。 对于 的数据,满足 。
0812
- Status
- Done
- Rule
- IOI
- Problem
- 4
- Start at
- 2024-8-12 9:00
- End at
- 2024-8-12 12:00
- Duration
- 3 hour(s)
- Host
- Partic.
- 26