有 \((n+m+k)\) 盏灯，各有不同的编号与开关。其中有 \(n\) 盏亮着的， \(m\) 盏暗灯， \(k\) 栈坏的灯。亮灯按下开关将变成暗灯，暗灯按下开关将变成亮灯，坏灯无论如何按开关都是暗灯。求操作严格 \(t\) 次后，所有灯都是暗灯的方案数。结果对 \(10^9+7\) 取模。
对于数列 \(\{a_n\}\) 设 \(EGF(a_n)=A^e(x)\) 表示其指数型生成函数
设 \(ans[t]\) 表示操作严格 \(t\) 次的方案数，不难写出方程：
考虑 \(t\) 个位置中，先选择 \(p\) 个位置给所有亮灯，再选 \(q\) 个位置给所有暗灯，最后选 \(r\) 个位置给所有坏灯
\(\displaystyle ans[t]=\sum_{p+q+r=t} \left( \begin{matrix} t \p,q,r \end{matrix} \right) f_n[p]g_m[q]k^r\)
其中：
\(f_n[p]\) 表示操作 \(p\) 次，让亮着的 \(n\) 盏灯全部变暗的方案数
\(g_m[q]\) 表示操作 \(q\) 次，让暗着的 \(m\) 盏灯全部仍是暗的方案数
考虑到 \(\displaystyle \left( \begin{matrix} t \p,q,r \end{matrix} \right)={t!\over p!\cdot q!\cdot r!\cdot(t-p-q-r)!},(t-p-q-r)!=0!=1\)
整理式子得 \(\displaystyle {ans[t]\over t!}=\sum_{p+q+r=t}{f_n[p]\over p!}\cdot {g_m[q]\over q!}\cdot {k^r\over r!}\)
因此有 \(Ans^e=F_n^e\cdot G_m^e\cdot EGF(k^r)\)
因为 \(\displaystyle EGF(k^r)=\sum_{r=0}^\infty {k^r\over r!}x^r=\sum_{r=0}^\infty {1\over r!}(kx)^r=e^{kx}\)
故接着考虑 \(F_n^e\) 与 \(G_m^e\)
对于 \(F_n^e\) ，我们不难列出转移式子：考虑第一个亮的灯按开关次数，显然必须按奇数次；则剩余 \((n-1)\) 个开关的方案数，等价于只有 \((n-1)\) 个开关的方案数
即 \(\displaystyle f_n[p]=\sum_{i=0}^p \left( \begin{matrix} p \i \end{matrix} \right)f_{n-1}[p-i][2\nmid i]\)
整理得到 \(\displaystyle {f_n[p]\over p!}=\sum_{i+j=p}{f_{n-1}[j]\over j!}\cdot {1^i- (-1)^i\over 2i!}\)
故两边取 EGF 得到 \(F_n^e=F_{n-1}^e\cdot ({e^x-e^{-x}\over 2})\)
原文：https://www.cnblogs.com/JustinRochester/p/13968872.html