danihao123's Blog

拉格朗日插值的模板题qwq

考虑\(f(n) = \sum_{i = 1}^n i^k\)，这显然是一个\(k + 1\)次多项式（通过差分之类的手段可以证明），然后我们发现\(g(n) = \sum_{i = 1}^n f(n)\)可以用类似手段证明是\(k + 2\)次多项式。类似的，我们会发现，答案是一个\(k + 3\)次多项式。

分别对\(g\)以及答案插值即可。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <climits>
typedef long long ll;
const ll ha = 1234567891LL;
int k;
ll a, n, d;
ll pf[205], pg[205], fac[205];
ll pow_mod(const ll &a, ll b) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b >> 1);
  ans = (ans * ans) % ha;
  if(b & 1LL) ans = (ans * a) % ha;
  return ans;
}
ll inv(ll v) {
  return pow_mod(v, ha - 2LL);
}

void process() {
  fac[0] = 1LL;
  for(int i = 1; i <= k + 5; i ++) {
    fac[i] = (fac[i - 1] * inv(i)) % ha;
#ifdef LOCAL
    printf("fac[%d] : %lld\n", i, fac[i]);
#endif
  }
  for(int i = 1; i <= k + 3; i ++) {
    pf[i] = (pf[i - 1] + pow_mod(i, k)) % ha;
#ifdef LOCAL
    printf("pf[%d] : %lld\n", i, pf[i]);
#endif
  }
  for(int i = 1; i <= k + 3; i ++) {
    pg[i] = (pg[i - 1] + pf[i]) % ha;
#ifdef LOCAL
    printf("pg[%d] : %lld\n", i, pg[i]);
#endif
  }
#ifdef LOCAL
  puts("Processing finished!");
#endif
}

ll g(ll x) {
  static ll sim_f[205], sim_g[205];
  sim_f[0] = 1LL;
  for(int i = 1; i <= k + 3; i ++) {
    sim_f[i] = (x - (ll(i)) + ha) % ha;
    sim_f[i] = (sim_f[i] * sim_f[i - 1]) % ha;
  }
  sim_g[k + 4] = 1LL;
  for(int i = k + 3; i >= 1; i --) {
    sim_g[i] = (x - (ll(i)) + ha) % ha;
    sim_g[i] = (sim_g[i] * sim_g[i + 1]) % ha;
  }
  ll ret = 0;
  for(int i = 1; i <= k + 3; i ++) {
    ll ans = (((pg[i] * sim_f[i - 1]) % ha) * sim_g[i + 1]) % ha;
    ans = (ans * fac[i - 1]) % ha;
    ans = (ans * fac[k + 3 - i]) % ha;
    if(1 & (k + 3 - i)) {
      ret = (ret - ans + ha) % ha;
    } else {
      ret = (ret + ans) % ha;
    }
  }
#ifdef LOCAL
  printf("g(%lld) : %lld\n", x, ret);
#endif
  return ret;
}
ll h(ll x) {
  static ll ph[205];
  ph[0] = g(a);
  for(int i = 1; i <= k + 4; i ++) {
    ph[i] = (ph[i - 1] + g(a + (ll(i)) * d)) % ha;
  }
  static ll sim_f[205], sim_g[205];
  sim_f[0] = 1LL;
  for(int i = 1; i <= k + 4; i ++) {
    sim_f[i] = (x - (ll(i)) + ha) % ha;
    sim_f[i] = (sim_f[i] * sim_f[i - 1]) % ha;
  }
  sim_g[k + 5] = 1LL;
  for(int i = k + 4; i >= 1; i --) {
    sim_g[i] = (x - (ll(i)) + ha) % ha;
    sim_g[i] = (sim_g[i] * sim_g[i + 1]) % ha;
  }
  ll ret = 0;
  for(int i = 1; i <= k + 4; i ++) {
    ll ans = (((ph[i] * sim_f[i - 1]) % ha) * sim_g[i + 1]) % ha;
    ans = (ans * fac[i - 1]) % ha;
    ans = (ans * fac[k + 4 - i]) % ha;
    if(1 & (k + 4 - i)) {
      ret = (ret - ans + ha) % ha;
    } else {
      ret = (ret + ans) % ha;
    }
  }
  return ret;
}

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    scanf("%d%lld%lld%lld", &k, &a, &n, &d);
    process();
    printf("%lld\n", h(n));
  }
  return 0;
}