POJ3734 Blocks （指数型生成函数）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了POJ3734 Blocks （指数型生成函数），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1523字，纯文字阅读大概需要3分钟。

内容图文

这题直接贴推公式图，多重集合的 n n n排列组合数的定理证明需自行了解

问题一般问得很明确，每个元素可以重复出现，但是每个又有特殊的限制，然而总量是固定的 n n n，问排列数量有多少个？（也就是给出了总数 和 每个物体的种数）

那么把公式推出来之后，基本上是套快速幂模板了。
But如果不走公式这条路（因为给的限制条件太少了，用个模拟就行了），也就是基本的模拟系数的乘法和加法。

例如下面这道HDU1521（这里补充暴力模拟展开系数解法）

值得注意的是：因为已经是暴力模拟了，出来的系数是 x n x^n xn 前面的系数，所以还要乘回 n ! n! n!，才是生成函数的系数，如果又懵了可以先回去卡看上面的公式图，如果还不懂说明定理的证明没搞明白。

题意：

n n n种物品，每种有 a i a_i ai?个，抽 m m m个的排列数？

思路：

回到常见提问：总量固定是 m m m个，而每个都有 a i a_i ai?个的限制

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50;
const int inf = 0x3f3f3f3f;

double jc[N], coef[N], tmp[N];
int v[N]; // 每件物品数 
int main()
{
	int n, m;
	jc[0] = 1;
	for (int i = 1; i <= 10; i++)
		jc[i] = jc[i - 1] * i;
	while (cin >> n >> m)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &v[i]);  // 每个物品最多能拿，也就是括号里的最高项
			v[i] = min(v[i], m);
		} 		
		memset(coef, 0, sizeof coef);
		memset(tmp, 0, sizeof tmp);
		
		for (int i = 0; i <= v[1]; i++)  // 赋coef初值是第一个物品 
		 	coef[i] = 1.0 / jc[i];
		
		for (int i = 2; i <= n; i++) // 后面 n - 1个括号 
		{
			for (int j = 0; j <= m; j++)  // m是前面被乘()的最高项
				for (int k = 0; k <= v[i] && k + j <= m; k++)
					tmp[k + j] += coef[j] * 1.0/ jc[k];
			memcpy(coef, tmp, sizeof tmp);
			memset(tmp, 0, sizeof tmp);
		}
		
		printf("%.lf\n", coef[m] * jc[m]);
	}
    return 0;
}

内容总结

以上是互联网集市为您收集整理的POJ3734 Blocks （指数型生成函数）全部内容，希望文章能够帮你解决POJ3734 Blocks （指数型生成函数）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---