Atcoder arc059
F - Unhappy Hacking
https://atcoder.jp/contests/arc059/tasks/arc059_d
操作 push(0),push(1),pop(),其中pop在空时也可以操作
给定0/1串,问有多少不同n次的操作序列 能得到s, 方案数mod1e9+7
n 5000
2s
256mb
我的思路
对于 开头 需要计算 多少次可以在空时pop的操作 得到长度0
对于 中间 需要计算 多少次不可以在空时pop的操作 得到长度0
那么 用生成函数表示
$[x^t]g_0(x)$ 表示 $t$次操作长度0的第一种操作
$[x^t]f_0(x)$ 表示 $t$次操作长度0的第二种操作
那么有$ans = [x^{n}] g_0(x) (\cdot x \cdot f_0(x))^{|s|}$
$= [x^{n}] g_0(x) \cdot x^{|s|} \cdot f_0(x)^{|s|}$
$= [x^{n-|s|}] g_0(x) \cdot f_0(x)^{|s|}$
后面直接多项式快速幂就好了，1e9+7 原根太小,没法ntt