P10780 BZOJ3028 食物题解

题意：

cxy 这次又要出去旅游了，和上次不同的是，她这次要去宇宙探险！我们暂且不讨论她有多么 NC，她又幻想了她应该带一些什么东西。理所当然的，你当然要帮她计算携带 $n$ 件物品的方案数。

她这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。

当然，她又有一些稀奇古怪的限制：

每种食物的限制如下：

承德汉堡：偶数个；

可乐：$0$ 个或 $1$ 个；

鸡腿：$0$ 个，$1$ 个或 $2$ 个；

蜜桃多：奇数个；

鸡块：$4$ 的倍数个；

包子：$0$ 个，$1$ 个，$2$ 个或 $3$ 个；

土豆片炒肉：不超过一个；

面包：$3$ 的倍数个；

注意，这里我们懒得考虑 cxy 对于带的食物该怎么搭配着吃，也认为每种食物都是以「个」为单位（反正是幻想嘛），只要总数加起来是 $n$ 就算一种方案。因此，对于给出的 $n$，你需要计算出方案数，并对 $10007$ 取模。

输入格式：

一个整数 $n$，表示总数。

输出格式：

一个整数，表示方案数模 $10007$。

数据范围：

对于所有数据，$1\leq n\leq 10^{500}$；

考虑生成函数：

汉堡偶数个，那么
$f_1(x)=\sum_{n \geq 0} x^{2 n} = \frac{1}{1-x^2}$
可乐 0/1 个，那么
$f_2(x)=x^0+x^1=1+x$
鸡腿 0/1/2 个，那么
$f_3(x)=1+x+x^2$
蜜桃多奇数个，那么
$f_4(x)=\sum_{n \geq 0} x^{2 n+1} = x\sum_{n \ge 0}x^{2n} = \frac{x}{1-x^2}$
鸡块 $4^k$ 个，那么
$f_5(x)=\sum_{n \geq 0} x^{4 n} = \frac{1}{1-x^4}$
包子 0/1/2/3 个，那么
$f_6(x)=1+x+x^2+x^3 = (1 + x) (1 + x^2)$
土豆片炒肉 0/1 个，那么
$f_7(x) = 1+x$
面包 $3^k$ 个，那么
$f_8(x) = \sum_{n \geq 0} x^{3 n}=\frac{1}{1-x^3}$

把上面这些 $f$ 全部乘起来，得到

$F(x) = x(1-x)^{-4}$

那么第 $n-1$ 项的系数为

$\binom{-4}{n-1}(-1)^{n-1} = \binom{n+2}{3} = \frac{n(n+1)(n+2)}{6}$

时间复杂度 $\mathcal{O}(\log_{10}n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

const int mod = 10007;
#define gc() getchar()
template<typename T> void read(T &k)
{
    k = 0; char ch = gc(); 
    while(isdigit(ch)) { k = (k * 10 + ch - '0') % mod; ch = gc(); }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; read(n); 
    printf("%lld\n", n * (n + 1) % mod * (n + 2) % mod * 1668 % mod);
    return 0;
}