食物

wjh15101051's space

卧薪尝胆，厚积薄发。

食物

Date: Thu Feb 28 17:18:35 CST 2019

In Category: NoCategory

Description：

给出了 $8$ 种食物和其个数的限制，问拿 $n$ 个食物有多少种方案。

$1\leqslant n\leqslant 10^{500}$

Solution：

最后的答案就是把每个的生成函数乘起来第 $n$ 项的系数。

$k$ 的倍数个： $f(x)=1+x^k+x^{2k}+\cdots=\frac1{1-x^k}$

不超过 $k$ 个： $f(x)=1+x+x^2+\cdots+x^k=\frac{1-x^{k+1}}{1-x}$

奇数个： $f(x)=x+x^3+x^5+\cdots=\frac x{1-x^2}$

最后乘起来的结果是 $f(x)=\frac x{(1-x)^4}$ 。

然后根据生成函数的知识我们知道这个的第 $n$ 项系数为： $\binom{n+2}3=\frac{(n+2)(n+1)n}6$ 。

Code：


#include<bits/stdc++.h>

using namespace std;

#define MOD 10007

int main()

{

	int n = 0;char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))n = ((n << 1) + (n << 3) + c - '0') % MOD,c = getchar();

	cout << 1ll * n * (n + 1) % MOD * (n + 2) % MOD * 1668 % MOD << endl;

	return 0;

}

In tag: 数学-组合数学-生成函数

wjh15101051