tkdsheep-solution-0002

从 Trac 迁移的文章

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

原文章内容如下：

{{{

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

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

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

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

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

然后就是有一个陷阱，给的m个限制条件可能是有重复的，必须去掉重复的，更新m的实际个数，否则容斥结果是错的

}}}

这题必须要先明确一个重要前提，每天必须看且只能一个章节
首先如果不考虑m个限制条件，每天可以看任意章节，则方案数为n!
现在有了m个限制条件，比如第i天不能看某些章节
那么我们就从所有方案数里减掉那些与限制条件有冲突的方案，由于限制条件有多个，可以用容斥原理
因为m只有25，所以可以对这m个条件进行枚举，枚举每个条件是否冲突，即2m（最多225）
直接用dp来枚举的话，以本题的case数+数据范围，需要40多秒才能跑完，一个剪纸的方法是dfs来枚举状态
利用最开始的重要前提：每天必须看且只能一个章节，所以有些限制条件不可能同时冲突，比如第2天不能看章节2和章节3
那么第二天要冲突的话只能选章节2【或者】章节3，这样就减掉了很多状态
具体dfs的写法参见192题库，很简单的，函数只需要2个参数，当前枚举到第几个限制条件，冲突了几个（用来确定容斥原理公式中加还是减） 
然后就是有一个陷阱，给的m个限制条件可能是有重复的，必须去掉重复的，更新m的实际个数，否则容斥结果是错的