【BZOJ 3028】食物

传送门

---

problem

有若干种物品，每种物品选取的限制如下：

• $A$A：偶数个
• $B$B：$0$0 个或 $1$1 个
• $C$C：小于等于 $2$2 个
• $D$D：奇数个
• $E$E：$4$4 的倍数个
• $F$F：$0$0个，$1$1 个，$2$2 个或 $3$3 个
• $G$G：不超过一个
• $H$H：$3$3 的倍数个

求从中选择n个物品的方案数模 $10007$10007 的结果。

数据范围：$n\le10^{500}$n≤10500。

---

solution

这道题重在思维，代码非常简单。

我们先把这 $8$8 种东西的生成函数搞出来，即：

• $A(x) =\sum_{i=0}^{\infty}x^{2i}=\frac{1}{1-x^2}$A(x)=∑i=0∞​x2i=1−x21​
• $B(x)=1+x$B(x)=1+x
• $C(x)=1+x+x^2$C(x)=1+x+x2
• $D(x)=\sum_{i=0}^{\infty}x^{2i+1}=\frac{x}{1-x^2}$D(x)=∑i=0∞​x2i+1=1−x2x​
• $E(x)=\sum_{i=0}^{\infty}x^{4i}=\frac{1}{1-x^4}$E(x)=∑i=0∞​x4i=1−x41​
• $F(x)=1+x+x^2+x^3$F(x)=1+x+x2+x3
• $G(x)=1+x$G(x)=1+x
• $H(x)=\sum_{i=0}^{\infty}x^{3i}=\frac{1}{1-x^3}$H(x)=∑i=0∞​x3i=1−x31​

然后把它们乘起来，化个简，发现乘积是 $\frac{x}{(1-x)^4}$(1−x)4x​。

现在的目标就是，把这个式子展开，然后求指数为 $n$n 时的系数。

泰勒展开

我们令 $f(x)=\frac{x}{(1-x)^4}$f(x)=(1−x)4x​，那把 $f(x)$f(x) 在 $0$0 处展开，得：

$f(x)=\sum_{i=0}^{\infty}\frac{f^{(i)}(0)}{i!}x^i$f(x)=i=0∑∞​i!f(i)(0)​xi

那么第 $n$n 项的系数就是 $\frac{f^{(n)}(0)}{n!}$n!f(n)(0)​。

莱布尼茨公式

$(uv)^{(n)}=\sum_{i=0}^n(^n_i)u^{(i)}v^{(n-i)}$(uv)(n)=i=0∑n​(in​)u(i)v(n−i)

我们令 $u=x,v=(1-x)^{-4}$u=x,v=(1−x)−4。

因为只有当 $i=1$i=1 时，$u'=1$u′=1（其它时候 $u^{(i)}=0$u(i)=0），所以我们只需要求 $v^{(n-1)}$v(n−1)。

根据高阶导数的公式，即 $(x^a)^{(n)}=(\prod_{i=0}^{n-1}(a-i))x^{a-n}$(xa)(n)=(i=0∏n−1​(a−i))xa−n

这个公式根据 $(x^a)'=ax^{a-1}$(xa)′=axa−1 化一化就可以推出来。

所以：

$v^{(n-1)}=(-1)^{n-3}\frac{(n+2)!}{6}$v(n−1)=(−1)n−36(n+2)!​

然后乘个 $n$n（因为 $(^n_1)=n$(1n​)=n），再除个 $n!$n!（看泰勒展开部分），得到：

$ans=(-1)^{n-3}\frac{n(n+1)(n+2)}{6}$ans=(−1)n−36n(n+1)(n+2)​

由于 $(-1)^{n-3}$(−1)n−3 只代表了第 $n$n 项的系数正负，不代表大小，可以直接忽略不计。

所以最终的答案就是：

$ans=\frac{n(n+1)(n+2)}{6}$ans=6n(n+1)(n+2)​

那把 $n$n 读进来直接算就可以了。

---

code

#include<cstdio>
#include<cctype> 
#include<cstring>
#include<algorithm>
#define P 10007
using namespace std;
const int inv6=1668;
int n=0;
int main(){
	char c=getchar();
	while(isdigit(c))  n=(n*10+(c^'0'))%P,c=getchar();
	printf("%d\n",1ll*n*(n+1)*(n+2)*inv6%P);
	return 0;
}