BZOJ3028 食物

传送门

BZOJ

题意描述

明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么$NC$，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带$N$件物品的方案数。他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等当然，他又有一些稀奇古怪的限制，每种食物的限制如下：

承德汉堡：偶数个
可乐：$0$个或$1$个
鸡腿：$0$个，$1$个或$2$个
蜜桃多：奇数个
鸡块：$4$的倍数个
包子：$0$个，$1$个，$2$个或$3$个
土豆片炒肉：不超过一个。
面包：$3$的倍数个
注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以‘个’为单位（反正是幻想嘛），只要总数加起来是$N$就算一种方案。因此，对于给出的$N$,你需要计算出方案数，并对$10007$取模。

输入输出格式

输入格式：

输入一个数字$N$，$1 \le n \le 10^{500}$

输出格式：

如题

输入输出样例

输入样例#1：

1

输出样例#1：

5

输入样例#2：

1

输出样例#2：

35

分析

菜鸡Gluttony写下这篇辣鸡题解避免自己忘记广义组合数和广义二项式定理。

首先这题是一道广为人知的生成函数题。
那么我们先列出生成函数。
注意一点，蜜桃多不能不选…

承德汉堡：$1+x^2+x^4+…=\frac{1}{1-x^2}$。
可乐：$1+x=\frac{1-x^2}{1-x}$。
鸡腿：$1+x+x^2=\frac{1-x^3}{1-x}$。
蜜桃多：$x+x^3+x^5+…=\frac{x}{1-x^2}$。
鸡块：$1+x^4+x^8+…=\frac{1}{1-x^4}$。
包子：$1+x+x^2+x^3=\frac{1-x^4}{1-x}$。
土豆片炒肉：$1+x=\frac{1-x^2}{1-x}$。
面包：$1+x^3+x^6+…=\frac{1}{1-x^3}$。

答案就是它们的生成函数乘起来。

$$\begin{align*} ans &=\frac{1}{1-x^2} \times \frac{1-x^2}{1-x} \times \frac{1-x^3}{1-x} \times \frac{x}{1-x^2} \times \frac{1}{1-x^4} \times \frac{1-x^4}{1-x} \times \frac{1-x^2}{1-x} \times \frac{1}{1-x^3} \\ &=\frac{x}{(1-x)^4} \end{align*}$$

那么似乎有两种差不多的化简方法（当然你也可以直接隔板法背结论）。

第一种——广义组合数

首先写一下广义组合数是什么。

$$\begin{align*} \binom{n}{m} &=\frac{\prod_{i=n-m+1}^{n}i}{m!} \\ &=\frac{\prod_{i=0}^{m-1}(n-i)}{m!} \\ \end{align*}$$

知道了广义组合数是什么之后我们开始化式子。

$$\begin{align*} \frac{x}{(1-x)^4} &=x(1-x)^{-4} \\ &=x\sum_{i=0}^{\infty}\binom{-4}{i}(-x)^i \\ &=x\sum_{i=0}^{\infty}\binom{-4}{i}(-1)^{i}x^i \\ &=\sum_{i=0}^{\infty}\binom{-4}{i}(-1)^{i}x^i \times x \\ &=\sum_{i=0}^{\infty}\binom{-4}{i}(-1)^{i}x^{i+1} \\ &=\sum_{i=1}^{\infty}\binom{-4}{i-1}(-1)^{i-1}x^{i} \\ \end{align*}$$

那么答案就是第$n$项的系数$\binom{-4}{n-1}(-1)^{n-1}$。

$$\begin{align*} \binom{-4}{n-1}(-1)^{n-1} &=\frac{\prod_{i=0}^{n-2}(-4-i)}{(n-1)!}(-1)^{n-1} \\ &=\frac{\prod_{i=0}^{n-2}(-1) \times (-4-i)}{(n-1)!} \\ &=\frac{\prod_{i=0}^{n-2}(4+i)}{(n-1)!} \\ &=\frac{(n+2)!}{3!(n-1)!} \\ &=\binom{n+2}{3} \end{align*}$$

第二种——广义二项式定理

骗你的，广义二项式定理就是二项式定理套上广义组合数。

但首先还是写一下广义二项式定理是什么（这里指指数为负整数的广义二项式定理）。

$$\begin{align*} (1-x)^{-n} &=\sum_{i=0}^{\infty}\binom{-n}{i}(-x)^{i} \\ &=\sum_{i=0}^{\infty}\binom{n+i-1}{i}x^{i} \\ &=\sum_{i=0}^{\infty}\binom{n+i-1}{n-1}x^{i} \\ \end{align*}$$

$(1+x)^{-n}$就是再乘上一个$(-1)^i$。

知道了广义二项式定理是什么之后我们开始化式子。

$$\begin{align*} \frac{x}{(1-x)^4} &=x(1-x)^{-4} \\ &=x\sum_{i=0}^{\infty}\binom{-4}{i}(-x)^i \\ &=x\sum_{i=0}^{\infty}\binom{4+i-1}{i}x^i \\ &=x\sum_{i=0}^{\infty}\binom{4+i-1}{3}x^i \\ &=\sum_{i=0}^{\infty}\binom{4+i-1}{3}x^i \times x \\ &=\sum_{i=0}^{\infty}\binom{4+i-1}{3}x^{i+1} \\ &=\sum_{i=1}^{\infty}\binom{4+i-2}{3}x^{i} \\ \end{align*}$$

那么答案就是第$n$项的系数$\binom{4+n-2}{3}=\binom{n+2}{3}$。

参考资料

本校大佬autoint的题解
qq_41157212的组合数学-广义组合数-广义阶乘-伽马函数
叶子心情你不懂的牛顿广义二项式定理-母函数
百度百科的二项式定理

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int p=10007;
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=(sum*10+cc-'0')%p;
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=(sum*10+cc-'0')%p,cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n;
int main()
{
	n=read<int>();
	printf("%lld\n",(1ll*n*(n+1)*(n+2)/6)%p);
    return 0;
}