题目大意
给定n,k，求把n!拆分成k个不同的正整数的乘积的方案数。（一种方案的排列仍是一种方案）。答案对 109+7 取模。
n≤10000 k≤30
时限为4s
分析
这是一道容斥好题。
首先可以不管算重，最终答案除以 k! 即可。
接下来考虑如何容斥。k个数互不相同，其实就相当于 k(k?1)2 个限制条件。如果一个方案不满足x个条件，那么它要乘上的容斥系数为 (?1)x
如果直接枚举不满足哪些，显然会超时。不妨转换一下：已知条件是形如(x,y)的，表示第x个数≠第y个数。把k个数看成k个点，限制(x,y)看成连接x,y的边。那么一个选择方案相当于选择一些边，使其变成许多个联通块。
好了，现在可以尝试枚举每个联通块的大小。这就相当于对k的整数拆分。为了避免算重，当前枚举的这一个数必须不小于前一个。跑出来，30能有5000多种拆法。那么整数拆分的方案数就可以接受了。接下来到下一步。
现在已经确定了k的一个整数拆分方案（即若干个联通块大小）。假设有m个联通块，第i个大小为 si 。它对答案的贡献是多少？这要考虑三个东西：
1. 把k个点分配到这些联通块的方案数。
2. 对应的分配边的所有方案对答案的贡献
3. 拆分 n! ，满足形成这些联通块的方案数。
它对答案的贡献就是三个数的乘积。现在一个个来考虑。
首先是第1部分 【容斥原理|【WC2017模拟1.22】简单题】这个比较简单。首先总的排列数有 k! 个。设在当前的整数拆分方案中，数字i出现了 pi 次，即 ∑i?pi=k 。那么对于拆出来的每个联通块 si ，这表示有 si 个数相同，就要除掉 si! ，接下来由于i出现了 pi 次，又要除掉 pi! 。最终得到：
Ans1=k!∑ki=1((i!)aiai!)
第2部分 对于每个联通块分别考虑。因为一条边的意义是两个数相同，所以一个联通块里的所有数都是相等的。那就可以直接考虑容斥系数的总和了。
设 S(n) 表示n个点的联通图的集合， e(G)表示图G的边数 。对于第i个联通块（大小为 si ），它对答案的贡献就是 ∑G∈S(si)(?1)e(G) 。
设 g(n) 等于n个点的联通图对答案的贡献。这个可以考虑用容斥计算，即全集减去不合法方案数。
首先考虑不合法的。其实就是n个点的不联通图。它形成了至少2个联通块。枚举编号为1的点所在的联通块大小，那么：
g(n)=f(n)?∑i=1n?1Cin?1f(n?i)g(i)
其中 f(n)表示n个点的
全集大小。
考虑 f(n) 的值。显然f(1)=1。当n>1，就会有 n(n?1)2 条可能出现的边。如果其中一条边出现了，容斥系数就乘-1，否则乘1。所有方案加起来后发现，当n>1时，f(n)=0！
上面的式子变成：
g(n)={0?(n?1)?g(n?1),1,n>1n=1
那么一个整数拆分方案第2部分的贡献为 Ans2=∏i=1mg(si)
最后是第3部分 首先给n!分解质因数。每个质因子都是相对独立的，就可以分开考虑。
对于一个质因子，设它共出现了 cnt 次，现在要把它分配到 m 个联通块里。一个联通块里的数要满足相同，每个质因子出现个数也一定要相同。所以对于si，它要在cnt份里占掉si的倍数份（可以是0）。这就是个完全背包问题了。
优化
为了提高运行效率，可能需要一些优化。
1. 递归对k进行拆分，然后做背包时相当于有m个物品。回溯的时候，前m-1个物品的答案要保留，不用每个方案都重新做一次dp
2. 假设k当前剩下x没有拆分，先枚举到x/2，再直接整个拆分
3. 适当去掉一些模运算
我的程序极限数据跑了3s左右
#include
#include
#include #define Min(a,b) ((a)<(b)?(a):(b))using namespace std;
const int N=10005,M=31,mo=1e9+7,NN=100000;
typedef long long LL;
int n,m,Fac[N],Inv[N],F_Inv[N],g[N],tot,p[N],f[M][NN],cnt[N],st[N],sum,ans;
bool bz[N];
void init()
{
scanf("%d%d",&n,&m);
for (int i=2;
i<=n;
i++)
{
if (!bz[i]) p[tot++]=i;
for (int j=0;
jm) return;
for (int i=0;
i 推荐阅读
- HDU 5519 Kykneion asma（沈阳站K题&&DP+容斥）
- 解题报告|51nod 1667 概率好题
- 树形dp|Codeforces 917D Stranger Trees 树形dp+容斥原理
- DP|[codeforces 917D]Stranger Trees
- [arc061F] Card Game for Three
- 容斥原理（翻译）