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;
}