定义

对于数列\(\{f_n\}\)，我们定义\(\tilde F(x)=\sum^\infty_{i=0}f_ix^i\)，并称\(\tilde F(x)\)为数列\(\{f_n\}\)的生成函数。

定义就这么点。

从这个定义可以看出，生成函数实际上就是在描述一个序列（其实你也可以把它当做集合）。

但实际应用中，生成函数可以比更加灵活，我们可以利用生成函数来表示状态集合，利用生成函数的性质来计数，求解数列等。 Continue reading

题面在这里

一个有\(N\)个元素的集合有\(2^N\)个不同子集（包含空集），现在要在这\(2^N\)个集合中取出若干集合（至少一个），使得它们的交集的元素个数为\(K\)，求取法的方案数，答案模\(1000000007\)。（是质数喔~）

反演概念

对于序列\(\{f_n\},\{g_n\}\)，我们可以找到一组关系，可以将\(\{f_n\}\)与\(\{g_n\}\)变换，这样的操作称为反演。

即\(\exists~\{a_{n,i}\},\{b_{n,i}\},s.t.\) \[ f_n=\sum^n_{i=0}{a_{n,i}g_i} \]

\[ g_n=\sum^n_{i=0}b_{n,i}f_i \]

两者等价。

PKU WC的游记 Continue reading

引子

这个方法是原来乱翻线代书(Linear Agebra Done Right)看到的，当时就觉得非常厉害，但由于要求积分，一直不知道怎么实现。现在好了，多项式学了， Simpson 自适应积分也会了。闲来无事填个坑。

题目在此

给定每种长度的贝壳数量\(A(i)\)，求长度为\(n\)的链的种数。