123
F
每一个条件都是一个以 \((0,0)\) 为一点的"纺锤"四边形，询问为查询某一点是否在某一连续段的 Minkowski 和。
由于本题四边形形态特殊，故可以不直接维护 Minkowski 和，转而维护上下凸包，若该点在上下凸包内，则其显然在 Minkowski 和内。考虑一段 \(i\sim j\) 的上凸包，发现一定是 \(j-i+1\) 斜率递减的斜线再加上水平线，并且按照斜率排序后，点为 \((u_i,v_i)\)，那么某一个斜线的起始点即为一段前缀和 \((\sum u, \sum v)\)。
于是对于每个询问可以考虑二分斜率求出答案，类似于待修改查第k大的问题，往上套一个整体二分就结束了。
J
答案表达式
\[ g(n)=\sum_{i=0}^{\lfloor \frac n2\rfloor}a^{n-2i}\binom{n}{2i}\frac {(2i)!}{i!2^i} \]
递推式
\[ g(n)=a\cdot g(n-1)+(n-1)\cdot g(n-2) \]
两种做法，要么用递推式直接跑整式递推模板，要么利用答案表达式观察出\(\frac {(2i)!}{i!2^i}\)在$2i>mod $时候为\(0\)，进而利用卢卡斯定理\(\binom{n}{2i}=\binom{n\%mod}{2i}\)，有
\[ g(n)=\sum_i a^{n-2i}\binom{n\%mod}{2i}\frac {(2i)!}{i!2^i}\newline=(a^{mod})^{n/mod}g(n\%mod)\newline =a^{n/mod}g(n\%mod) \]
3s足够根据递推式暴力求出\(mod\)以内的\(g(n)\)。
注：答案的生成函数为 \(H=e^{x^2/2+ax}\)，对其求导可得 \((x+a)H=H'\)，写开来后即可得到递推式。
更一般地，可以说若序列生成函数为 exp 则序列存在整式递推，为分式则序列存在线性递推。
upd：整式递推模板added