排列组合与dp的小总结
排列组合与dp的小总结
题型A：相同者不相邻的方案数
题目代表：球球的排列 /湫秋系列故事——安排座位 。
dp方程式：
int sum=num[1];
dp[1][num[1]-1]=1;
for(int i=2;i<=cnt;i++){//枚举当前到达的系
for(int j=0;j<sum;j++){//枚举当前的空隙（不合法地方的数量）
for(int k=1;k<=num[i];k++){//枚举当前体系的人
for(int h=0;h<=j&&h<=k;h++){//枚举在这个空隙下放的人数（我要填补的空袭）
dp[i][j-h+num[i]-k] += dp[i-1][j]*C(j,h)%mod*C(sum+1-j,k-h)%mod*C(num[i]-1,k-1)%mod;
dp[i][j-h+num[i]-k]%=mod;
}
}
}
sum+=num[i];
}
int ret=dp[cnt][0];
for(int i=1;i<=cnt;i++){
ret*=fac[num[i]];
ret%=mod;
}
题型B：其他
- 吉夫特 ：
重要结论：C(n,m)当且仅当n&m=m时，为奇数。
直接暴力每一个数开头的答案即可，枚举子集在n的三次方左右 - Division into Two
一个好想法的dp,最开始我的想法是f(i,j,k)表示前i个数，第i个数选择k(0/1)，前一个数选择j(0/1)的方案数，但是不合法情况难以统计
我们发现一个集合确定后另外一个就确定了，相当于有一个限制，可以从这方面入手dp - 卡农
没有想到竟然利用容斥原理：
简化题目：
选择m个n排列的子序列，要求子序列间互不相同，要求数字1-n出现次数都为偶数次（0也算），求方案数
设计dp_i表示选择i个子集且满足条件的方案数，答案就是dp_m
考虑转移，用容斥原理
首先，对于任意一个i，前面i-1个子集选定了，那么这个根据奇数偶数就可以定下来了，于是总的方案数就是
前一个 任选的方案数，为A(2的n次方-1,i-1)
减去第一种不合法条件：我这一次选到了空集，那么前面必然要求是一个合法的排列，即-f[i-1]
减去第二种不合法条件：出现了重复子集的选择,那么就是：
f[i-2](i-1)(2^n -i +1)
- 123 Triangle
看起来就像杨辉三角是吧，符号+-轮流很简单，但是显然要是想往回推系数会很难。
然而杨辉三角和排列组合是有关系的，在n的时间复杂度内可以暴力。
但是还有一种思路：从他给的数字是1/2/3这方面考虑。