母函数
Posted On 2019年1月28日
Description
母函数又称生成函数，是一类用来解决组合问题计数的方法。一般类似背包DP的计数问题可以使用此方法。
HDU 1085
构造母函数\(G(x)=(x^0+x^1+x^2..)\cdot (x^0+x^2+x^4…)\cdot (x^0+x^5+x^{10}…)\)
最低的系数为0的项\(x^i\)即为所求
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <set> #include <cstring> #include <algorithm> #include <map> #include <queue> #include <cstdio> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1100+100; int n[3]; ll tmp[maxn*3],aw[maxn*10]; signed main() { for (int i=0;i<3;i++)n[i]=read(); while (n[0]||n[1]||n[2]) { memset(tmp,0,sizeof(tmp)); memset(aw,0,sizeof(aw)); for (int i=0;i<=n[0];i++) for (int j=0;j<=n[1];j++) ++tmp[i+j*2]; for (int i=0;i<=n[0]+n[1]*2;i++) for (int j=0;j<=n[2];j++) aw[i+j*5]+=tmp[i]; int up=n[0]+n[1]*2+n[2]*5; for (int i=0;i<=up+1;i++) if (!aw[i]) { printf("%d\n",i); break; } for (int i=0;i<3;i++)n[i]=read(); } } |
HDU 1521
同理构造母函数\(G(x)=(1+\frac{x^1}{1!}+\frac{x^2}{2!}+…+\frac{x^{cnt_1}}{cnt_1!})(1+\frac{x^1}{1!}+\frac{x^2}{2!}+…+\frac{x^{cnt_2}}{cnt_2!})….\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <set> #include <cstring> #include <algorithm> #include <map> #include <queue> #include <cstdio> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e5+100; int n,m,cnt[maxn]; double xi[10][maxn],now[maxn]; inline bool get() { return scanf("%d%d",&n,&m)!=EOF; } inline int min(const int a,const int b){return a<b?a:b;} ll fac[maxn]; signed main() { fac[0]=1; for (int i=1;i<=100;i++)fac[i]=fac[i-1]*i; while (get()) { for (int i=0;i<n;i++)cnt[i]=read(); memset(xi,0,sizeof(xi)); for (int i=0;i<n;i++) for (int j=0;j<=cnt[i];j++) xi[i][j]=1.0/fac[j]; int up=cnt[0]; for (int i=1;i<n;i++) { memset(now,0,sizeof(now)); for (int j=0;j<=min(m,up);j++) for (int k=0;k<=cnt[i]&&k+j<=m;k++) now[j+k]+=xi[i-1][j]*xi[i][k]; memcpy(xi[i], now, sizeof(now)); up+=cnt[i]; } printf("%.0lf\n",xi[n-1][m]*fac[m]); } } |
Subscribe
0 评论