题意
给定序列({a_i}_{i=1}^k)和({b_i}_{i=1}^k)。考虑一个序列({F_i}_{i=1}^infty)，满足(n>k):
你需要找到一个序列({c_i}_{i=1}^k)，其满足(n>b_k):
(1 leq k leq 128)，(1 leq a_i leq 10^9)，(1 leq b_1 < b_2 < dots < b_k leq 10^9)。
结果对(10^9+7)取模。
做法
令，
(F(x)=sumlimits_{i=1}^{infty} f_ix^i)，(A(x)=1-sumlimits_{i=1}^k a_ix^i)，(B(x)=1-sumlimits_{i=1}^k c_ix^{b_i})，
(P(x)=sumlimits_{i=1}^{k}f_ix^i)，(Q(x)=sumlimits_{i=1}^{b_k}f_ix^i)。
有，
整理，
引理：有解的充要条件为(A(x))是(B(x))的因子。
证明：
充分性显然。
考虑证明必要性，假设(C(x)=frac{B(x)}{A(x)})最高有效项(>b_k-k)，则一定存在(P(x))使得(P(x)C(x))最高有效项(>b_k)，故矛盾。
那么有(B(x)mod A(x)=0)
即(1-sumlimits_{i=1}^k c_i(x^{b_i}mod A(x))=0)。
(1-sumlimits_{i=1}^k c_i(x^{b_i}mod A(x))=1-sumlimits_{i=1}^k c_isum limits_{j=0}^{k-1}d_{i,j}x^j=0)，可以列出(k)个等式，直接高斯消元即可。
复杂度(O(k^3+k^3log b))或(O(k^3+k^2log b))，取决于(x^{b_i}mod A(x))的复杂度。