A simple Blog for wyx I've been down the bottle hoping.
HDU 5275 牛顿插值
发表于: | 分类: Oi | 评论:0 | 阅读:64

给你一坨点,然后指定 $[l,r]$ 一坨点在 $pos$ 处的取值

牛顿插值裸题,先 $n^2$ 处理差商,然后每次 $O(n)$ 求一遍就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3000+5;
const int mod = 1e9+7;
const int Max = 250000+5;
LL inv[Max];
LL F[N][N], X[N];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

inline int get(int x) {
    if(x < 0) return -inv[-x];
    return inv[x];
}

void init() {
    inv[1] = 1;
    for(int i=2;i<=Max-5;++i) inv[i] = (LL)(mod - mod/i)*inv[mod%i] % mod;
}

int main() {
//  freopen("tt.in", "r", stdin);
    init();
    int n = read();
    for(int i=1;i<=n;++i) X[i] = read(), F[i][1] = read();
    for(int len=2;len<=n;++len) {
        for(int i=1;i+len-1<=n;++i) {
            F[i][len] = (F[i][len-1]-F[i+1][len-1]) % mod * get(X[i]-X[i+len-1]) % mod;
            ((F[i][len] %= mod) += mod ) %= mod;
        }
    }
    int q = read();
    for(int i=1;i<=q;++i) {
        int l = read(), r = read(), tmp = read();
        LL ans = 0, now = 1;
        for(int j=l;j<=r;++j) {
            (ans += (LL)now * F[l][j-l+1] % mod) %= mod;
            now = now * (tmp-X[j]) % mod;
            now %= mod;
            now += mod;
            now %= mod;
        }
        printf("%I64d\n", ans);
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP