生成函数初步

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

这个大坑不知道要填多久

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

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

好了看例题：

食物 - BZOJ by HydroOJ - P3028

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

$$\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提供的快读 */