笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

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

posted on 2019-01-29 20:48:42 | under 题解 |

题意大概就是给出连续的一段$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)$

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 ;
}