题解 AT1184 【見たことのない多項式】
皎月半洒花
2019-01-29 20:48:42
题意大概就是给出连续的一段$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 ;
}
```