2012-0002

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

再占一个 by大肥羊 此坑必填@.@

这题必须要先明确一个重要前提，每天必须看且只能一个章节

首先如果不考虑m个限制条件，每天可以看任意章节，则方案数为n!

现在有了m个限制条件，比如第i天不能看某些章节，那么我们就从所有方案数里减掉那些与限制条件有冲突的方案，由于限制条件有多个，可以用容斥原理

因为m只有25，所以可以对这m个条件进行枚举，枚举每个条件是否冲突，即2^m^（最多2^25^）

直接这样枚举的话，以本题的case数+数据范围，需要40多秒才能跑完，一个剪纸的方法是dfs来枚举状态，利用最开始的重要前提：每天必须看且只能一个章节，所以有些限制条件不可能同时冲突，比如第2天不能看章节2和章节3，那么第二天要冲突的话只能选章节2【或者】章节3，这样就减掉了很多状态，具体dfs的写法参见192题库，很简单的，函数只需要2个参数，当前枚举到第几个限制条件，冲突了几个（用来确定容斥原理公式中加还是减）


~~不过这个剪枝，个人感觉有点坑，如果数据极端一点，每天只有一个限制条件，那么还是要40多秒才能跑出来，建议月赛的时候把m=25改到20左右~~

我错了。。原来那个直接枚举跑40秒是因为还要再乘一个m的复杂度~于是dfs是正解

再占一个 by大肥羊 此坑必填@.@

这题必须要先明确一个重要前提，每天必须看且只能一个章节

首先如果不考虑m个限制条件，每天可以看任意章节，则方案数为n!

现在有了m个限制条件，比如第i天不能看某些章节，那么我们就从所有方案数里减掉那些与限制条件有冲突的方案，由于限制条件有多个，可以用容斥原理

因为m只有25，所以可以对这m个条件进行枚举，枚举每个条件是否冲突，即2^m（最多2²⁵）

直接这样枚举的话，以本题的case数+数据范围，需要40多秒才能跑完，一个剪纸的方法是dfs来枚举状态，利用最开始的重要前提：每天必须看且只能一个章节，所以有些限制条件不可能同时冲突，比如第2天不能看章节2和章节3，那么第二天要冲突的话只能选章节2【或者】章节3，这样就减掉了很多状态，具体dfs的写法参见192题库，很简单的，函数只需要2个参数，当前枚举到第几个限制条件，冲突了几个（用来确定容斥原理公式中加还是减）

不过这个剪枝，个人感觉有点坑，如果数据极端一点，每天只有一个限制条件，那么还是要40多秒才能跑出来，建议月赛的时候把m=25改到20左右

我错了。。原来那个直接枚举跑40秒是因为还要再乘一个m的复杂度~于是dfs是正解