ARC093F Dark Horse 【容斥,状压dp】
题目链接:gfoj
神仙计数题。
可以转化为求\(p_1,p_2,\ldots,p_{2^n}\),使得\(b_i=\min\limits_{j=2^i+1}^{2^{i+1}}p_j\)都不属于\(a_i\)。
日常容斥。设\(f(S)\)表示\(i\in S\Rightarrow b_i\in A\)的答案,则答案就是\(ans=\sum_S(-1)^{|S|}f(S)\)。
求\(f(S)\)使用状压dp。设\(f[i][S]\)表示将\(a_i\)从大到小排序,\(b_i\)在\(a\)中出现的下标\(i\)组成的集合\(S\),方案数是多少。
初值\(f[0][0] = 1\)。
如果\(a_{i+1}\)不在\(b_i\)中出现,则\(f[i+1][S]\leftarrow f[i][S]\)。
如果\(a_{i+1}\)在\(b_i\)中出现,枚举\(a_{i+1}=b_k\),那么我们要在\(2^n-S-a_i\)个数中选出\(2^k-1\)个数被\(a_{i+1}\)打掉,组成排列\((2^k)!\)种方案,那么\(f[i+1][S|2^k]\leftarrow f[i][S]\times \dbinom{2^n-S-a_i}{2^k-1}\times (2^k)!\)。
然后你发现我们并没有把不在\(b_i\)中出现的\(S\)这些数没有乘上,所以\(f(S)=f[m][S]\times S!\)。然后抄个柿子上去,时间复杂度\(O(nm2^n)\)。
code
```cpp
#include
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 16, mod = 1e9 + 7;
int n, m, a[N], f[N + 1][1 = mod) a -= mod;}
inline int kasumi(int a, int b){
int res = 1;
while(b){
if(b & 1) res = (LL) res * a % mod;
a = (LL) a * a % mod; b >>= 1;
}
return res;
}
inline void init(int m){
fac[0] = 1;
for(Rint i = 1;i ()); init((1 > k) & 1))
upd(f[i + 1][S | (1
最新文章
- linux网卡混杂模式
- Linux的课程总结
- Angularjs 服务注册
- 关于sql 的convert 格式设置
- HttpClient_javax.net.ssl.SSLHandshakeException: sun.security.validator 问题解决,与环境有关
- selenium+python笔记6
- RocketMQ术语[转]
- win7 64位下jboss配置
- 转发:使用sql命令查询视图中所有引用的基础表
- Hadoop学习之Mapreduce执行过程详解
- AngularJs学习笔记1——总体介绍
- threadpool源码学习
- python中assert详解
- Android MediaPlayer接口及状态迁移
- nginx命令行参数和信号
- C++实现 逆波兰表达式计算问题
- java中的引用类型 部分讲解
- Python Socket多线程并发
- Kali之aircrack-ng
- Unix网络编程 3.9 readline函数