首页 > 试题广场 >

宝石装箱

[编程题]宝石装箱
颗宝石装进个箱子使得每个箱子中都有一颗宝石。第颗宝石不能装入第个箱子。求合法的装箱方案对取模。
两种装箱方案不同当且仅当两种方案中存在一颗编号相同的宝石装在不同编号的箱子中。

输入描述:
第一行一个整数。
第二行个整数。


输出描述:
输出一行一个整数表示答案。
示例1

输入

2
1 2

输出

1

说明

只有一种合法的装箱方案{2,1}。
示例2

输入

2
1 1

输出

0

说明

没有合法的方案。
示例3

输入

8
7 3 3 2 5 4 1 8

输出

14568

备注:
算法知识视频讲解
开通博客
头像 Lskkkno1
发表于 2020-05-22 22:00:21
宝石装箱 题目描述 有 个带标号盒子和球，每个球都有一个盒子 不能放进去（ 不一定是排列）。 问每一个盒子里都有一个球的方案数。 正解 每一个球都有一个限制（一个盒子不能放）。 这个问题类似于错排，而错排有一种容斥的解法。 设 表示至少有 条限制不满足的方案数, 表示恰好有 条限制不满 展开全文
去ta的博客 赞 (9) 回复(4) 收起
头像 lalalaterraria
发表于 2020-05-23 12:10:29
这里给出一种容斥+多项式的做法 复杂度为是n^2/2 大家一般是容斥+背包啊，我觉得这里多项式也蛮好写的。 容斥应该不用多说了，设为第i个球合法的情况。套一套下面两个公式。 我们要求的是第二个公式的左半，用第一个公式带入第二个公式的右边第二项。 所得公式的右半边从左向右数第i项(不考虑符号)，表 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 氧气少年Kevin
发表于 2022-06-21 11:14:11
牛客5633D - 宝石装箱 链接：https://ac.nowcoder.com/acm/contest/5633/D 知识点：线性容斥、背包DP 难度：蓝 题意 将 nnn 个物品装进 nnn 个箱子，每个箱子恰好装一个物品。 要求第 iii 个物品不能装入第 aia_iai​ 个箱子 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
0条回答 22浏览

热门推荐

相关试题

宝石装箱

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号