写在前面
这玩意没有顺序，大致按难度排序。
没有毒瘤多项式科技！！
里面全部是幼儿园数数题，老年选手也可颐养身心。
正文——数数
1. 「Luogu2012」拯救世界2
- 题意：......
- 做法：
由于不是组合，所以不能够用 OGF，于是我们考虑 EGF。
对于A,C,G,T四种： \(G_1(i)=\sum\limits_{i=0}^{\infty}\frac{x^i}{i!}=e^x\)
对于乾、坎、艮、震： \(G_2(i)=\sum\limits_{i=0}^{\infty}\frac{x^{2i}}{(2i)!}=\frac{1}{2}(e^x+e^{-x})\) （\(e^{-x}=\sum\limits_{i=0}^{\infty}\frac{(-1)^ix^i}{i!}\)，两个相加即可抵消奇数）。
剩下那种： \(G_3(i)=\sum\limits_{i=0}^{\infty}\frac{x^{2i+1}}{(2i+1)!}=e^x-G_2(x)=\frac{1}{2}(e^x-e^{-x})\)
于是：
然后我们要求的是 \(G(x)\) 中 \(x^n\) 的系数：
\[\because e^{ax}=\sum\limits_{i=0}^{\infty}\frac{a^ix^i}{i!},[x^n]e^{ax}=\frac{a^n}{n!} \] \[\begin{aligned}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\therefore G(x)ans&=n![x^n]G(x)\\&=\frac{1}{2^8}(12^n-4\times8^{n}+6\times 4^{n}-4+(-1)^{n}\times4^n)\end{aligned} \]然后这道毒瘤题还要用欧拉定理：
\[a^b\equiv a^{b\mod \varphi(p)}\mod p \]然后我们知道 \(\varphi(10^9)=4\times10^8\)。
先取模，然后快速幂即可。
当 \(n\le 4\) 的时候由于无法计算 \(2^8\) 的逆元，所以要单独拎出来判断。
2. 「ARC096C」Everything on It
- 题意：
有 \(n\) 种酱。你需要若干碗拉面，满足：
你可以在每碗拉面上放若干种酱，也可以不放，容易发现方案数为 \(O(2^n)\)。
不能出现放的酱一样的两碗拉面。每一种酱至少在两碗拉面中加了。
求拉面集合的方案数。答案对给定的质数取模。
\(n\leq 3000\)，时限 \(\texttt{4s}\)。 - 做法：
题目答案无法简单统计，于是考虑容斥，令 \(f(x)\) 为 \(x\) 个数不合法的方案数，那么答案就是 \(\sum\limits_{x=0}^{n}(-1)^xf(x)\)。
接下来计算 \(f(x)\)：
首先选出这 \(x\) 个不合法的数，总共 \(\dbinom{n}{x}\) 种方案。
然后设把这些数选出来后扔到 \(y\) 个集合里，因为不合法，所以每个 \(x\) 至多出现一次。每个集合互不相同，不难想到斯特林数。
但是斯特林数是必须扔进 \(y\) 集合，而根据刚刚的分析，对于每个 \(x\)，我们可以选择扔或不扔。我们创建一个集合 \(y+1\) 表示所有不扔到 \(1\) 到 \(y\) 集合的 \(x\)，这样对于每一个 \(x\)，都必须扔到 \(1\) 到 \(y+1\) 中。又因为斯特林数要求集合非空，所以对应地创建一个 \(x+1\) 的数扔进集合 \(y+1\) 中。
于是由斯特林数的组合意义我们知道 \(x\) 个数，扔进 \(y\) 个集合，每个 \(x\) 至多出现一次，每个集合互不相同的方案数即 \(\begin{Bmatrix}x+1\\y+1\end{Bmatrix}\) 种。
剩下 \(n-x\) 个数，每个数选或不选可以组成 \(2^{n-x}\) 个集合，往前面的 \(y\) 个集合加有 \({(2^{n-k})}^y\) 种方案，每个集合出不出现又可以有 \(2^{2^{n-x}}\) 种方案。
所以 \(f(x)=\dbinom{n}{x}2^{2^{n-x}}\sum\limits_{y=0}^{i}(2^{n-x})^y\begin{Bmatrix}x+1\\y+1\end{Bmatrix}\)。
带入最初的式子，得到：
\(O(n^2)\) 预处理斯特林数，\(O(n)\) 预处理阶乘、逆元、阶乘逆元，然后就可以 \(O(n^2)\) 计算答案啦！