BZOJ3028 食物
题面
链接
题目描述
明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带 (N) 件物品的方案数。他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等当然，他又有一些稀奇古怪的限制：每种食物的限制如下：
承德汉堡：偶数个
可乐：(0)个或(1)个
鸡腿：(0)个，(1)个或(2)个
蜜桃多：奇数个
鸡块：(4)的倍数个
包子：(0)个，(1)个，(2)个或(3)个
土豆片炒肉：不超过一个。
面包：(3)的倍数个
注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以 个 为单位（反正是幻想嘛），只要总数加起来是 (N) 就算一种方案。因此，对于给出的 (N)，你需要计算出方案数，并对 (10007) 取模。
输入
输入一个数字 (N, 1 leq n leq 10^{500})
输出
如题
输入样例
5
输出样例
35
题解
生成函数入门题
推导
-
承德汉堡 (f_1)
承德汉堡：偶数个
即为数列 (langle 0, 2, 4, 6, cdots angle) 的生成函数
[ f_1(x) = sum_{n geq 0} x^{2n} ]求出其封闭形式
[ egin{align} f_1(x) cdot x^2 + x^0 &= sum_{n geq 0} x^{2(n + 1)} + x^0 \ &= sum_{n geq 1} x^{2n} + x^0 \ &= f_1(x) end{align} ][ herefore f_1(x) cdot (x^2 - 1) = -1 \ herefore f_1(x) = frac{1}{1 - x^2} ] -
可乐 (f_2)
可乐：0个或1个
即为数列 (langle 0, 1 angle) 的生成函数
[ f_2(x) = sum_{n in {0, 1}} x^n ]其封闭形式为
[ f_2(x) = x^0 + x^1 = 1 + x ] -
鸡腿 (f_3)
鸡腿：0个，1个或2个
同
2.可乐理即为数列 (langle 0, 1, 2 angle) 的生成函数
[ f_3(x) = 1 + x + x^2 ] -
蜜桃多 (f_4)
蜜桃多：奇数个
即为数列 (langle 1, 3, 5, 7 cdots angle) 的生成函数
[ f_4(x) = sum_{n geq 0} x^{2n + 1} ]求出其封闭形式
[ egin{align} f_4(x) cdot x^2 + x &= sum_{n geq 0} x^{2(n + 1) + 1} + x \ &= sum_{n geq 1} x^{2n + 1} + x \ &= f_4(x) end{align} ][ herefore f_4(x) cdot (x^2 - 1) = -x \ herefore f_4(x) = frac{x}{1 - x^2} ] -
鸡块 (f_5)
鸡块：4的倍数个
即为数列 (langle 0, 4, 8, 12, cdots angle) 的生成函数
[f_5(x) = sum_{n geq 0} x^{4n} ]求出其封闭形式
[ egin{align} f_5(x) cdot x^4 + x^0 &= sum_{n geq 0} x^{4(n + 1)} + x^0 \ &= sum_{n geq 1} x^{4n} + x^0 \ &= f_5(x) end{align} ][ herefore f_5(x) cdot (x^4 - 1) = -1 \ herefore f_5(x) = frac{1}{1 - x^4} ] -
包子 (f_6)
包子：0个，1个，2个或3个
同
2.可乐理即为数列 (langle 0, 1, 2, 3 angle) 的生成函数
[ f_6(x) = 1 + x + x^2 + x^3\ ]因式分解，得
[ f_6(x) = (1 + x)(1 + x^2) ] -
土豆片炒肉 (f_7)
土豆片炒肉：不超过一个。
同
2.可乐[ f_7(x) = f_2(x) = 1 + x ] -
面包 (f_8)
面包：3的倍数个
[ f_8(x) = sum_{n geq 0} x^{3n} ]求其封闭形式
[egin{align} f_8(x) cdot x^3 + x^0 &= sum_{n geq 0} x^{3(n + 1)} + x^0 \ &= sum_{n geq 1} x^{3n} + x^0 \ &= f_8(x) end{align} ][ herefore f_8(x) cdot (x^3 - 1) = -1 \ herefore f_8(x) = frac{1}{1 - x^3} ]
综上
( f_1(x) = frac{1}{1 - x^2} \ f_2(x) = 1 + x \ f_3(x) = 1 + x + x^2 \ f_4(x) = frac{x}{1 - x^2} \ f_5(x) = frac{1}{1 - x^4} \ f_6(x) = (1 + x)(1 + x^2) \ f_7(x) = 1 + x \ f_8(x) = frac{1}{1 - x^3} \ )
乘积为
展开，得
化简，得
由二项式定理
得：
第 (n) 项对应 (i = n - 1)，其系数即为：
反转上指标[1]
即方案数为
细节
-
由于输入的 (n) 范围为 (10^{500}) 需要在输入时取模
[ ecause overline{n_1 n_2 n_3 cdots n_{f - 1} n_f} = 10 overline{n_1 n_2 n_3 cdots n_{f - 1}} + n_f\ herefore overline{n_1 n_2 n_3 cdots n_{f - 1} n_f} = 10(10(cdots (10n_1 + n_2) cdots) + n_{f - 1}) + n_f \ herefore overline{n_1 n_2 n_3 cdots n_{f - 1} n_f} equiv (10((10((cdots (10n_1 + n_2) mod M cdots) mod M) + n_{f - 1}) mod M) + n_f) mod M (mod M) ]伪代码
/* 输入的数为 n n 的各位为 n[1 ... f] ans = n % MOD */ Function Read() for i <- 1 to f do ans <- (ans * 10 + n[i]) % MOD end Return ans -
要求 (frac{n(n + 1)(n + 2) mod M}{6}) 需要用到费马小定理求出乘法逆元
[ frac{n(n + 1)(n + 2) mod M}{6} = (n(n + 1)(n + 2) mod M) cdot (6^{M - 2} mod M) ]这里可以选择写带取模快速幂，也可以直接算出 (6^{M - 2} mod M)
当 (M = 10007) 时：
[ 6^{M - 2} mod M = 1668 ]
代码
C++
#include <iostream>
#include <cstdio>
const int MOD = 10007;
inline int read()
{
char ch;
int res = 0;
ch = std::getchar();
while (ch >= '0' and ch <= '9')
{
res = (res * 10 + ch - '0') % MOD;
ch = std::getchar();
}
return res;
}
int main()
{
int n;
n = read();
std::cout << ((n * (n + 1) % MOD) * (n + 2) % MOD) * 1668 % MOD;
return 0;
}
Python3
MOD = 10007
n = int(input())
print(n * (n + 1) * (n + 2) * 1668 % MOD)