题面
有 ((n+m+k)) 盏灯，各有不同的编号与开关。其中有 (n) 盏亮着的， (m) 盏暗灯， (k) 栈坏的灯。亮灯按下开关将变成暗灯，暗灯按下开关将变成亮灯，坏灯无论如何按开关都是暗灯。求操作严格 (t) 次后，所有灯都是暗灯的方案数。结果对 (10^9+7) 取模。
(n,mleq 5 imes 10^3,t,kleq 10^{18})
记号规定
对于数列 ({a_n}) 设 (EGF(a_n)=A^e(x)) 表示其指数型生成函数
分析
设 (ans[t]) 表示操作严格 (t) 次的方案数，不难写出方程：
考虑 (t) 个位置中，先选择 (p) 个位置给所有亮灯，再选 (q) 个位置给所有暗灯，最后选 (r) 个位置给所有坏灯
(displaystyle ans[t]=sum_{p+q+r=t} left( egin{matrix} t \ p,q,r end{matrix} ight) f_n[p]g_m[q]k^r)
其中：
(f_n[p]) 表示操作 (p) 次，让亮着的 (n) 盏灯全部变暗的方案数
(g_m[q]) 表示操作 (q) 次，让暗着的 (m) 盏灯全部仍是暗的方案数
考虑到 (displaystyle left( egin{matrix} t \ p,q,r end{matrix} ight)={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^rover r!})
因此有 (Ans^e=F_n^ecdot G_m^ecdot EGF(k^r))
因为 (displaystyle EGF(k^r)=sum_{r=0}^infty {k^rover r!}x^r=sum_{r=0}^infty {1over 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( egin{matrix} p \ i end{matrix} ight)f_{n-1}[p-i][2 mid i])
整理得到 (displaystyle {f_n[p]over p!}=sum_{i+j=p}{f_{n-1}[j]over j!}cdot {1^i- (-1)^iover 2i!})
故两边取 EGF 得到 (displaystyle F_n^e=F_{n-1}^ecdot ({e^x-e^{-x}over 2}))
又因为 (displaystyle f_1[p]=[2 mid p]Rightarrow F_1^e={e^x-e^{-x}over 2})
因此递推得到 (displaystyle F_n^e=F_1^ecdot ({e^x-e^{-x}over 2})^{n-1}=({e^x-e^{-x}over 2})^n)
对于 (G_m^e) ，我们同样考虑第一个暗灯按开关只能为偶数次，故同样可列出转移方程：
(displaystyle g_m[q]=sum_{i=0}^qleft( egin{matrix} q \ i end{matrix} ight)g_{m-1}[q-i][2mid q])
同样整理可得 (displaystyle {g_m[q]over q!}=sum_{i+j=q}{g_{m-1}[j]over j!}cdot {1^i+(-1)^iover 2i!})
因此 (displaystyle G_m^e=G_{m-1}^ecdot ({e^x+e^{-x}over 2}))
同样因为 (displaystyle g_1[q]=[2mid q]Rightarrow G_1^e={e^x+e^{-x}over 2})
故同样的 (displaystyle G_m^e=G_1^ecdot ({e^x+e^{-x}over 2})^{m-1}=({e^x+e^{-x}over 2})^m)
回到原式，我们现在得到了：
(displaystyle Ans^e(x)=({e^x-e^{-x}over 2})^ncdot ({e^x+e^{-x}over 2})^mcdot e^{kx})
将右边展开得 (displaystyle Ans^e(x)={(e^{2x}-1)^ncdot (e^{2x}+1)^mover 2^{n+m}}cdot e^{(k-n-m)x})