在车人的要求下，玉帛拿一下午讲了生成函数

这个大坑不知道要填多久

前置知识：求导（真够让人头大）

这是讲解：懒得写了，全英文但勉强能看

好了看例题：

食物 - BZOJ by HydroOJ - P3028

如果看了上面的资料，那这就十分板了呀

f1=11−x2f2=1+xf3=1+x+x2f4=x1−x2f5=11−x4f6=1+x+x2+x3f7=1+xf8=11−x3<a1,a2,a3…an>⟷11−x2(1+x)(1+x+x2)x1−x211−x4(1+x+x2+x3)(1+x)11−x3=1(1+x)(1−x)(1+x)(1+x+x2)x(1+x)(1−x)x(1+x2)(1+x)(1−x)(1+x2)(1+x)(1+x)1(1−x)(1+x+x2)=x(1−x)4=x(1−x)−4=x∑k≥0(−4k)(−x)kai=(−4i−1)(−1)i−1=(i+2i−1)=(i+23)=i(i−1)(i−2)6\begin{aligned} &f1=\frac{1}{1-x^2}\\ &f2=1+x\\ &f3=1+x+x^2\\ &f4=\frac{x}{1-x^2}\\ &f5=\frac{1}{1-x^4}\\ &f6=1+x+x^2+x^3\\ &f7=1+x\\ &f8=\frac{1}{1-x^3}\\ &<a_1,a_2,a_3\dots a_n>\longleftrightarrow \frac{1}{1-x^2}( 1+x)( 1+x+x^2) \frac{x}{1-x^2} \frac{1}{1-x^4}( 1+x+x^2+x^3)( 1+x) \frac{1}{1-x^3}\\ &=\frac{1}{(1+x)(1-x)}(1+x)(1+x+x^2)\frac{x}{(1+x)(1-x)}\frac{x}{(1+x^2)(1+x)(1-x)}(1+x^2)(1+x)(1+x)\frac{1}{(1-x)(1+x+x^2)}\\ &=\frac{x}{(1-x)^4}\\ &=x(1-x)^{-4}\\ &=x\sum_{k\ge0}\binom{-4}{k} (-x)^k\\ \\ &a_i=\binom{-4}{i - 1}(-1)^{i-1}\\ &=\binom{i+2}{i-1}=\binom{i+2}{3}=\frac{i(i-1)(i-2)}{6} \end{aligned}

注意处理输入，需要逐位读入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// problem: #3028. 食物
// date: 2024.4.19-14:40
#include <bits/stdc++.h>
#define int long long
#define fish signed
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f, mod = 1e4 + 7;
int n;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=((x<<1)%mod+(x<<3)%mod+(ch^48)%mod)%mod;
		ch=getchar();
	}
	return (f*x%mod+mod)%mod;
}
fish main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    // ios::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    n=read();
    cout << (n * (n + 1) % mod * (n + 2) % mod * 1668 % mod) % mod;
    return 0;
}
/* 感谢@Symbolize提供的快读 */