Description

\\n【题意】# [国家集训队] 礼物
\\r\\n一年一度的圣诞节快要来到了。每年的圣诞节小 E 都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小 E 心目中的重要性不同，在小 E 心中分量越重的人，收到的礼物会越多。
\\r\\n小 E 从商店中购买了 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人礼物数量为 $w_i$。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模 $P$ 后的结果。
\\r\\n
\\r\\n【输入格式】
\\r\\n输入的第一行包含一个整数 $P$，表示模数。
\\r\\n第二行包含两个整数 $n$ 和 $m$，分别表示小 E 从商店购买的礼物数和接受礼物的人数。
\\r\\n第 $3$ 到第 $(m + 2)$ 行，每行一个整数，第 $(i + 2)$ 行的整数 $w_i$ 表示送给第 $i$ 个人的礼物数量。
\\r\\n
\\r\\n【输出格式】
\\r\\n若不存在可行方案，则输出 `Impossible`，否则输出一个整数，表示模 $P$ 后的方案数。
\\r\\n
\\r\\n【样例输入 #1】
\\r\\n100
\\r\\n4 2
\\r\\n1
\\r\\n2
\\r\\n
\\r\\n【样例输出 #1】
\\r\\n12
\\r\\n
\\r\\n【样例输入 #2】
\\r\\n100
\\r\\n2 2
\\r\\n1
\\r\\n2
\\r\\n
\\r\\n【样例输出 #2】
\\r\\nImpossible
\\r\\n
\\r\\n【样例 1 解释】
\\r\\n以 `/` 分割，`/` 前后分别表示送给第一个人和第二个人的礼物编号。$12$ 种方案详情如下：
\\r\\n```plain
\\r\\n1/23 1/24 1/34
\\r\\n2/13 2/14 2/34
\\r\\n3/12 3/14 3/24
\\r\\n4/12 4/13 4/23
\\r\\n```
\\r\\n【数据规模与约定】
\\r\\n设 $P= \\\\prod_{i=1}^t p_i^{c_i}$，$p_i$ 为质数。
\\r\\n对于 $15\\\\%$ 的数据，$n\\\\leq 15$，$m\\\\leq 5$，$p_i^{c_i}\\\\leq 10^5$。
\\r\\n在剩下的 $85\\\\%$ 数据中，约有 $60\\\\%$ 的数据满足 $t\\\\leq 2$，$c_i=1$，$p_i\\\\leq 10^5$，约有 $30\\\\%$ 的数据满足 $p_i\\\\leq 200$。
\\r\\n对于 $100\\\\%$ 的数据，$1\\\\leq n\\\\leq 10^9$，$1\\\\leq m\\\\leq 5$，$1\\\\leq p_i^{c_i}\\\\leq 10^5$，$1\\\\leq w_i \\\\leq P\\\\leq 10^9$。
\\r\\n

统计

递交统计

*【组合数：拓展Lucas定理】礼物[国家集训队]

信息

状态

开发

支持

关于

还没有账户？

登录