题解 [牛客练习赛64 D] 宝石装箱

宝石装箱

https://ac.nowcoder.com/acm/contest/5633/D

题目描述

个带标号盒子和球,每个球都有一个盒子 不能放进去( 不一定是排列)。

问每一个盒子里都有一个球的方案数。

正解

每一个球都有一个限制(一个盒子不能放)。

这个问题类似于错排,而错排有一种容斥的解法。

表示至少 条限制不满足的方案数, 表示恰好 条限制不满足的方案数。(一种方案必须放满所有盒子)

先钦定 个盒子一定不合法,然后其他盒子随便摆,这就是至少 个盒子不合法的方案数

那么有 :

特别的,


现在问题变成了如何求

可能有多个 相同,但是只能有一个球放进这个 这个盒子,设 为有多少个球不能放进第 个盒子里。

对于每一个 分开考虑,于是每一个 可以看成系数为 的物品,跑一遍背包就能求出 "先钦定 个位置不合法" 的方案数。

这还没完,钦定完一些位置不合法,还要考虑上其他位置,需要乘上一个阶乘才是至少有 个位置不合法的方案数。

最后答案?显然就是 呀。

总结

为什么要容斥

因为 "至少" 比 "恰好" 限制更少,更好求,于是要容斥。

"至少" 与 "恰好" 的关系怎么推得,为什么是这个关系

这个组合数不是很显然吗?

这个我只能说熟能生巧,做多了可能就记住了这个容斥系数了。

代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;
const int N = 8005;

int n;
int a[N], b[N];
int f[N], fac[N], ifac[N];

inline int fpm(int x, int y) {
    int r = 1;
    while(y) {
        if(y & 1) r = 1LL * r * x % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return r;
}

inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; }
inline int comb(int x, int y) { return 1LL * perm(x, y) * ifac[y] % mod; }

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        ++b[a[i]];
    }

    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = 1LL * i * fac[i - 1] % mod;
    ifac[n] = fpm(fac[n], mod - 2);
    for(int i = n; i; --i) ifac[i - 1] = 1LL * i * ifac[i] % mod;

    f[0] = 1;
    for(int i = 1; i <= n; ++i) {
        if(!b[i]) continue;
        for(int j = n; j >= 1; --j)
            f[j] = (f[j] + 1LL * b[i] * f[j - 1]) % mod;
    }

    for(int i = 0; i <= n; ++i)
        f[i] = 1LL * f[i] * fac[n - i] % mod;
    for(int i = n; i >= 0; --i)
        for(int j = i - 1; j >= 0; --j)
            f[j] = (f[j] - 1LL * comb(i, j) * f[i] % mod + mod) % mod;
    printf("%d\n", f[0]);
    return 0;
}
全部评论
想问下上面的g[i]为什么不等于f[i]-f[i+1]
1 回复 分享
发布于 2020-05-22 23:21
大佬,有个点不能理解就是为什么有些时候会求出负数啊?方案数怎么能等于负的呢,怎么理解负数的意义呢?
点赞 回复 分享
发布于 2020-10-06 15:10
涨知识了,🤩
点赞 回复 分享
发布于 2020-05-22 22:10
容斥写太少了,这个都是现推的qwq
点赞 回复 分享
发布于 2020-05-22 22:04

相关推荐

码农索隆:这种hr,建议全中国推广
点赞 评论 收藏
分享
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
9
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务