笨蛋花的小窝qwq

笨蛋花的小窝qwq

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

拉格朗日插值(求系数版)

posted on 2020-04-01 18:40:01 | under 题解 |

水题解水题解

发现在许多题里面的拉插需要求系数,但这个题只求第 $k$ 项,就比较无能。于是来写一个求系数的题解。

好了别喷了我知道我把这题做成了一道模拟题

大概就是考虑拉格朗日插值的formula:

$$f=\sum y_i\prod_{i\not=j}\frac{x-x_j}{x_i-x_j}$$

然后根据这个模拟多项式运算即可。其中需要注意的是多项式除法,在除一个类似 $(x+t)$ 的式子的时候,用到的是大除法(即手算多项式除法)的方式进行,也不是很难推,模拟一下就好了。

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;

const int N = 1000010 ;
const int P = 998244353 ;

int n, k ;

void debug(int *tp, int minn, int maxn, char c){
    for (int i = minn ; i <= maxn ; ++ i)
        cout << tp[i] << " " ;  cout << c ;
}

namespace Interpolation{
    int ans ;
    int now ;
    int x[N] ;
    int y[N] ;
    int fac[N] ;
    int inv[N] ;
    int pres[N] ;
    int sufs[N] ;
    int expow(int a, int b){
        int res = 1 ;
        a = (a % P + P) % P ;
        while (b){
            if (b & 1)
                res = (ll)res * a % P ;
            a = (ll)a * a % P ; b >>= 1 ;
        }
        return res ;
    }
    int fz[N] ;
    int fm[N] ;
    int tmp[N] ;
    int res[N] ;
    void add(int &a, int b){
        a += b ;
        if (a > P) a -= P ;
    }
    void dec(int &a, int b){
        (a -= b) %= P ;
        if (a < 0) a += P ;
    }
    void fmul(int *t, int deg, int opt){
    //次数为deg的多项式t乘上一个形如(x+opt)的多项式
        for (int i = deg + 1 ; i >= 1 ; -- i)
            tmp[i] = t[i], t[i] = t[i - 1] ;
        for (int i = 1 ; i <= deg + 1 ; ++ i)
            add(t[i], (ll)opt * tmp[i] % P) ;
    }
    void fdiv(int *t, int *ret, int deg, int opt){
    //次数为deg的多项式除以一个形如(x+opt)的多项式(整除)
        for (int i = 1 ; i <= deg ; ++ i) tmp[i] = t[i] ;
        for (int i = deg - 1 ; i >= 1 ; -- i)
            ret[i] = tmp[i + 1], dec(tmp[i], (ll)tmp[i + 1] * opt % P) ;
    }
    void get_xs(int n){//求系数
        fz[1] = 1 ;
        for (int i = 1 ; i <= n ; ++ i)
            fmul(fz, i, (-x[i] + P) % P) ;
        //debug(fz, 1, n + 1, '\n') ;
        for (int i = 1 ; i <= n ; ++ i){
            int fenmu = 1 ;
            for (int j = 1 ; j <= n ; ++ j)
                if (i != j) fenmu = (ll)fenmu * (x[i] - x[j] + P) % P ;
            fdiv(fz, fm, n + 1, -x[i]) ;
            fenmu = (ll)y[i] * expow(fenmu, P - 2) % P ;
        //  cout << fenmu << endl ;
            for (int j = 1 ; j <= n ; ++ j)
                add(res[j], (ll)fenmu * fm[j] % P) ;
        //  debug(res, 1, n, '\n') ;
        }
    }
    void pre_do(int U){
        fac[0] = 1 ;
        for (int i = 1 ; i <= U ; ++ i)
            fac[i] = (ll)fac[i - 1] * i % P ;
        inv[U] = expow(fac[U], P - 2) ;
        for (int i = U ; i >= 1 ; -- i)
            inv[i - 1] = (ll)inv[i] * i % P ;
        //debug(fac, 1, U, '\n') ;
        //debug(inv, 1, U, '\n') ;
    }
    int evenmark(int x){
        return (x & 1) ? -1 : 1 ;
    }
    void get_dnx(int n, int k, bool m){
        if (m){//求单独的一项,给出的x连续
            pre_do(n) ;
            pres[0] = 1, sufs[n + 1] = 1 ;
            for (int i = 1 ; i <= n ; ++ i)
                pres[i] = ((ll)pres[i - 1] * (k - x[i]) % P + P) % P ;
            for (int i = n ; i >= 1 ; -- i)
                sufs[i] = ((ll)sufs[i + 1] * (k - x[i]) % P + P) % P ;
            for (int i = 1 ; i <= n ; ++ i){
                now = (ll)pres[i - 1] * sufs[i + 1] % P ;
                now = (ll)now * expow((ll)fac[i - 1] * fac[n - i] % P, P - 2) % P ;
                now = (ll)evenmark(n - i) * y[i] % P * now % P ; ans = (ll)(ans + now) % P ;
            }
        }
        else {//求单独的一项,给出的x不连续
            int inow = 1 ;
            pres[0] = 1, sufs[n + 1] = 1 ;
            for (int i = 1 ; i <= n ; ++ i)
                pres[i] = ((ll)pres[i - 1] * (k - x[i]) % P + P) % P ;
            for (int i = n ; i >= 1 ; -- i)
                sufs[i] = ((ll)sufs[i + 1] * (k - x[i]) % P + P) % P ;
            for (int i = 1 ; i <= n ; ++ i){
                inow = 1, now = (ll)pres[i - 1] * sufs[i + 1] % P ;
                for (int j = 1 ; j <= n ; ++ j)
                    if (i != j) inow = (ll)inow * ((x[i] - x[j]) % P + P) % P ;
                ans = (ans + (ll)now * expow(inow, P - 2) % P * y[i] % P) % P ;
            }
        }
    }
}

int main(){
    cin >> n >> k ;
    using namespace Interpolation ;
    for (int i = 1 ; i <= n ; ++ i){
        cin >> x[i] >> y[i] ;
        if (x[i] == k) return cout << y[i], 0 ;
    }
    get_xs(n) ; //debug(res, 1, n + 1, '\n') ;
    for (int i = n + 1 ; i >= 1 ; -- i)
        ans = ((ll)ans * k % P + res[i]) % P ;
    cout << ans << '\n' ; return 0 ;
}