题解 AT1184 【見たことのない多項式】

皎月半洒花

2019-01-29 20:48:42

Solution

题意大概就是给出连续的一段$x_0$和$y_0$,算出多项式$F(x)$在一个特定值$x_0'$时的值。 我们注意到$40 \%$的数据可以直接高消,列出$n+1$个方程。 同时,我们还可以用朴素的拉格朗日插值法插出$80pts$的好成绩。 而对于$100 \%$的数据,$n$是$1e5$级别的,所以考虑预处理出一些东西。 我们观察拉格朗日插值公式的一般形式:$$F(x) = \sum \limits _{i=0}^{N} y_i \cdot \prod \limits_{i \neq j} \frac{x -x_j}{x_i-x_j}$$ 我们发现首先分子可以$O(n)$预处理,而分母由于$x_j$是连续的,所以$\rm{\prod \limits _{i \neq j} x_i - x_j}= fac(i) \cdot fac(N-i) \cdot evenmark(N-i)$,其中$fac$表示求阶乘,$\rm{evenmark}$是符号函数,当$N-i$是偶数时返回$1$,否则返回$-1$。 于是我们就可以得出一个式子: $$F(x) = \sum \limits_{i=0}^{N}{y_i \cdot}\frac{\frac{Pre}{x-i}}{fac(i) \cdot fac(N-i) \cdot evenmark(N-i)}$$其中$\frac{Pre}{x-i}$的缘由可以参考我的代码。 取模啥的就小费马搞一搞即可,最终复杂度$\Theta(n \log n)$ ```cpp inline LL expow(LL A, LL B){ LL res = 1 ; while (B){ if (B & 1) (res *= A) %= Mod ; B >>= 1, (A *= A) %= Mod ; } return res % Mod ; } inline LL get_symbol(LL x){ return (!x ? 1 : Mod - 1) ; } int main(){ cin >> N ; Fac[0] = qwq = 1 ; for (i = 0 ; i <= N ; ++ i) scanf("%lld", &base[i]), (Fac[i + 1] = Fac[i] * (i + 1)) %= Mod ; cin >> T ; Ans = 0 ; if (T <= N) return printf("%lld\n", base[T]) ; for (i = 0 ; i <= N ; ++ i) (qwq *= (T - i + Mod)) %= Mod ; for (i = 0 ; i <= N ; ++ i){ M = (N - i) & 1, _qwq = qwq * expow((T - i), Mod - 2) % Mod ; t = expow(Fac[i] * Fac[N - i] % Mod, Mod - 2) % Mod ; t = t * (get_symbol(M) * _qwq % Mod) % Mod, t = (t * base[i]) % Mod ; (Ans += t) %= Mod ; // cout << Ans << endl ; } printf("%lld\n", Ans) ; return 0 ; } ```