51nod-1258 序列求和 V4（拉格朗日插值法）

​​51nod-1258 序列求和 V4​​

題目

題目給出

，讓求

。

可以看出

分析

首先先分析

取前幾位 1, 2, 3時：

可以看出S函數是

次多項式，

根據 ​​拉格朗日插值法​​，由

個點可以确定這個多項式。直接帶入 n 求解即可

複雜度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 5e4 + 10;

int t;
ll n, k;

//求過 (xi, yi) 的多項式
ll inv[N];          //逆元
ll a[N];            //前 k+2 項自然數 k 次幂和   也就是yi
ll pre[N], suf[N];  //字首積 字尾積
ll fac[N];          //階乘的逆元

ll q_pow(ll x, ll y){
    ll ans = 1;
    while(y){
        if(y&1)
            ans = ans * x % mod;
        x = x * x % mod, y >>= 1;
    }
    return ans;
}

ll solve(ll x){         //前 x 項和
    if(x <= k+2)        //直接傳回
        return a[x];
    x %= mod;
    ll ans = 0;
    pre[0] = suf[k + 3] = 1;    //邊界
    for(ll i = 1; i <= k+2; i++){      //(x-i) 字首積
        pre[i] = pre[i - 1] * (x - i) % mod;    
    }
    for (ll i = k+2; i >=1 ; i--){   //(x-i) 字尾積
        suf[i] = suf[i + 1] * (x - i) % mod;    
    }
    for(ll i = 1; i <= k+2; i++){
        ll f = fac[i - 1] * fac[k + 2 - i] % mod;
        f = (k + 2 - i) & 1 ? -f : f;           //判斷正負
        (ans += a[i] * f % mod * pre[i - 1] % mod * suf[i + 1]) %= mod;
    }
    ans += ans < 0 ? mod : 0;
    return ans;
}

int main()
{
    cin >> t;
    for(ll i = 1; i < N; i++){     //預處理逆元
        inv[i] = q_pow(i, mod - 2);
    }
    fac[0] = 1;
    for(int i = 1; i < N; i++){     //預處理階乘逆元
        fac[i] = fac[i - 1] * inv[i] % mod;
    }
    while(t--){
        cin >> n >> k;                        //O(50000)
        for (ll i = 1; i <= k+2; i++){       //預處理前 k+2 項自然數 k 次幂和  
            a[i] = (a[i - 1] + q_pow(i, k)) % mod;
        }
        cout << solve(n) << endl;
    }
    return 0;
}