seo 网站分析/免费推广产品的平台

介绍

对于一些很复杂/凑数的组合题目，我们用普通的生成函数，特别是那些涉及二项式系数的数列，这是因为ta有二项式定理的形式
现在针对排列问题，我们有“指数生成函数”这种东西，即对于一个无穷数列h，他的指数生成函数g(x)定义为
$g(x)=\sum _{n=0}^{inf} {x^n\over n!}=h_1+h_2x+h_3{x^2\over2!}+...$
然后一些套路图直接引用这个up的啦

T1

POJ3734 Blocks

题意

用红黄蓝绿给n个格子染色，要求红色和绿色必须是偶数个，求方案数。对10007取模。

思路

涉及到了排列问题，我们用指数型生成函数
其实套路跟普通的生成函数一样了，只不过列的初始柿子不一样了

$$(1+{x^2\over2!}+{x^4\over4!}...)^2(1+x+{x^2\over2!}+{x^3\over3!}...)^2=({e^x+e^{-x}\over 2})^2e^{2x}={e^{4x}+2e^{2x}+1\over 4}$$
我们知道 $e^x=1+x+{x^2\over2!}+{x^3\over3!}+...=\sum _{n=0}^{inf}{x^n\over n!}$
那么 $e^{4x}=\sum _{n=0}^{inf}{(4x)^n\over n!}=\sum _{n=0}^{inf}4^n{x^n\over n!}$
继续化简原式 $${e^{4x}+2e^{2x}+1\over 4}={1\over 4}+\sum _{n=0}^{inf}{4^n+2^{n+1}\over 4}{x^n\over n!}$$
那么填n个格子依然是第n项的系数，即 ${4^n+2^{n+1}\over 4}$

代码

#include <cstdio>
#define LL long long
using namespace std;
const int mod=10007;
LL ksm(LL a,int k)
{LL ans=1;for (;k;k>>=1,a=a*a%mod)if (k&1) ans=ans*a%mod;return ans;
}
int main()
{int T,n;scanf("%d",&T);LL inv=ksm(4,mod-2);while (T--){scanf("%d",&n);printf("%d\n",(ksm(4,n)+ksm(2,n+1))%mod*inv%mod);}
}

T2

HDU1521 排列组合

思路

中文题？！
还是可以根据套路列出柿子

$$(1+x+{x^2\over2!}+{x^3\over3!}+...+{x^{m_1}\over m_1!})(1+x+{x^2\over2!}+{x^3\over3!}+...+{x^{m_2}\over m_2!})...$$
依然是求第m项的系数，暴力展开求解
但是要记住，我们求的第m项的系数是 $$\sum_{n=0}^{inf}a{x^n\over n!}$$ 中的a，所以答案要乘上mul[m]
a数组记得要清零

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
double mul[50],a[50],b[50];int v[15];
int main()
{mul[0]=1;for (int i=1;i<=10;i++) mul[i]=mul[i-1]*i;int n,m;while (scanf("%d%d",&n,&m)!=EOF){for (int i=1;i<=n;i++) scanf("%d",&v[i]),v[i]=min(v[i],m);memset(b,0,sizeof(b));memset(a,0,sizeof(a));for (int i=0;i<=v[1];i++) a[i]=1.0/mul[i];for (int i=2;i<=n;i++){for (int j=0;j<=m;j++)for (int k=0;k<=v[i];k++) b[j+k]+=a[j]*1.0/mul[k];for (int j=0;j<=m;j++) a[j]=b[j],b[j]=0;}printf("%.0lf\n",a[m]*mul[m]);}
}