文章目录

20231004 五校联考 frac 做题笔记

发布于

题意

给定长度为 $n$ 的数组 $a$ 和 $b$,有 $q$ 次询问,每次询问给定整数 $l, r, x$,求
$$\sum\limits_{i = l}^r\frac{a_i}{b_i + x}$$

$1 \leq 3\times 10^5, 1 \leq q, a_i, b_i \leq 10^6$
精度 $10^{-6}$ 时限 4 s

题解

好题,可以先思考一下

查看题解
$$\sum\limits_{i = l}^r\frac{a_i}{b_i + x}$$
对 $f\left(x\right) = \dfrac a{b + x}$ 进行 麦克劳林展开。
展开具体过程
根据 麦克劳林级数公式:
$$f\left(x\right) = \sum\limits_{n = 0}^\infin \frac{f^{\left(n\right)}\left(0\right)}{n!}x^n$$

首先,$f\left(x\right) = \dfrac a{b + x}$

然后,我们可以先对 $f\left(x\right) = \dfrac a{b + x}$ 求导,得到 $f'\left(x\right) = -\dfrac a{\left(b + x\right)^2}$,根据公式,取 $x = 0$,得到 $f'\left(0\right) = -\dfrac a{b^2}$。

接下来,对 $f'\left(x\right) = -\dfrac a{\left(b + x\right)^2}$ 求导,得到 $f''\left(x\right) = \dfrac{2a}{\left(b + x\right)^3}$,根据公式,取 $x = 0$,得到 $f''\left(0\right) = -\dfrac{2a}{b^3}$。

之后在求一项,$f'''\left(x\right) = -\dfrac{6a}{\left(b + x\right)^4}$,就可以发现规律了。

$$f^{\left(n\right)} = \left(-1\right)^n \cdot \frac{a\cdot n!}{\left(b + x\right)^{n + 1}}$$

带入 麦克劳林级数公式 得到:


$$f\left(x\right) = \sum\limits_{n = 0}^\infin \left(-1\right)^n \cdot \frac{a \cdot x^n}{b^{n+1}}$$

写成不用 $\Sigma$ 的形式:
$$\frac ab - \frac{a x}{b^2} + \frac{a x^2}{b^3} - \frac {a x^3}{b^4} + \frac {a x^4}{b^5} - \frac {a x^5}{b^6} + \frac {a x^6}{b^7} - \frac{a x^7}{b^8} + \cdots$$

精度不需要太高,算十几项足以。接着做前缀和,这样对于一个固定的 $x$,查一段区间的 $\dfrac{a_i}{b_i + x}$ 和就只需要常数时间了,但要线性时间预处理。

在 $\dfrac a{b + x}$ 中,$x$ 越大,对答案的影响越小。我们可以让 $h$ 从 $1$ 开始,每次增加 $25\%$,对于每个 $x$ 在 $\left[h, 1.25h\right)$ 之间的询问,把所有 $x$ 都当做 $h$ 算答案即可。

代码

// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom code.

// #define EFILE ""
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define _CONSOLE 0
#define _MULTI_TESTS 0

using namespace std;
using tp = long long;
constexpr tp ZERO = 0, ONE = 1, INF32 = -1u >> 2, INF = -1ull >> 2;

// :\

namespace _IO {
constexpr size_t BUF = 217217;
unsigned long long h = 5;
char ibuf[BUF], obuf[BUF];
char *li, *ri, *lo = obuf, *ro = obuf + BUF, st[100], *tp = st;
FILE *Istream = stdin, *Ostream = stdout;

char GC() {
#if _CONSOLE
  return getchar();
#endif
  if (li == ri) {
    li = ibuf; ri = li + fread(li, 1, BUF, Istream);
    if (li == ri) return '\n';
  }
  return *li++;
}

void _flush() {
  fwrite(obuf, 1, lo - obuf, Ostream);
  lo = obuf;
}

void PC(char ch) {
#if _CONSOLE
  return (void)putchar(ch);
#endif
  if (lo == ro) _flush();
  *lo++ = ch;
}

template <typename Type>
void r_int(Type& x) {
  bool neg = 0;
  char ch = GC();
  while (ch < 48 || ch > 57) { neg ^= ch == 45; ch = GC(); }
  for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
  if (neg) x = -x;
}

template <typename Type>
void r_uint(Type& x) {
  char ch = GC();
  while (ch < 48 || ch > 57) ch = GC();
  for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
}

template <typename Type>
void r_db(Type& x) {
  bool neg = 0;
  char ch = GC();
  while (ch < 48 || ch > 57) { neg ^= ch == 45; ch = GC(); }
  for (x = 0; ch >= '0' && ch <= '9'; ch = GC()) x = x * 10 + (ch & 15);
  if (ch == '.') {
    double p = 1;
    for (ch = GC(); ch >= '0' && ch <= '9'; ch = GC()) x = x + (p /= 10) * (ch & 15);
  }
  if (neg) x = -x;
}

template <typename Type>
void w_uint(Type x) {
  if (!x) { PC('0'); return; }
  while (x) { *tp++ = x % 10; x /= 10; }
  while (tp > st) PC(*--tp ^ 48);
}

template <typename Type>
void w_int(Type x) {
  if (x < 0) { PC('-'); w_uint(-x); }
  else w_uint(x);
}

template <typename Type>
void w_db(Type x) {
  double l = floor(abs(x));
  string s;
  if (x < 0) { PC('-'); x = -x; }
  x -= l;
  if (!l) PC(48);
  while (l) { s.push_back(l - floor(l / 10) * 10); l = floor(l / 10); }
  for (auto i = s.rbegin(); i != s.rend(); ++i) PC(*i ^ 48);
  PC(46);
  for (unsigned long long f = 0; f < h; ++f) {
    x *= 10;
    PC(floor(x - floor(x / 10) * 10) + 48);
  }
}

struct IO {
  IO& operator>>(char& x) { do { x = GC(); } while (x == 32 || x == 10 || x == 13); return *this; }
  IO& operator>>(string& x) {
    char c;
    operator>>(c);
    x = c;
    for (c = GC(); c != 32 && c != 10 && c != 13; c = GC()) x.push_back(c);
    x.shrink_to_fit();
    return *this;
  }
  IO& operator>>(short& x) { r_int(x); return *this; }
  IO& operator>>(int& x) { r_int(x); return *this; }
  IO& operator>>(long& x) { r_int(x); return *this; }
  IO& operator>>(long long& x) { r_int(x); return *this; }
  IO& operator>>(unsigned short& x) { r_uint(x); return *this; }
  IO& operator>>(unsigned int& x) { r_uint(x); return *this; }
  IO& operator>>(unsigned long& x) { r_uint(x); return *this; }
  IO& operator>>(unsigned long long& x) { r_uint(x); return *this; }
  IO& operator>>(float& x) { r_db(x); return *this; }
  IO& operator>>(double& x) { r_db(x); return *this; }

  IO& operator<<(short x) { w_int(x); return *this; }
  IO& operator<<(int x) { w_int(x); return *this; }
  IO& operator<<(long x) { w_int(x); return *this; }
  IO& operator<<(long long x) { w_int(x); return *this; }
  IO& operator<<(unsigned short x) { w_uint(x); return *this; }
  IO& operator<<(unsigned int x) { w_uint(x); return *this; }
  IO& operator<<(unsigned long x) { w_uint(x); return *this; }
  IO& operator<<(unsigned long long x) { w_uint(x); return *this; }
  IO& operator<<(char x) { PC(x); return *this; }
  IO& operator<<(const string& x) { for (auto& i : x) PC(i); return *this; }
  IO& operator<<(float& x) { w_db(x); return *this; }
  IO& operator<<(double& x) { w_db(x); return *this; }
  void flush() { _flush(); }
  void precision(unsigned long long p) { h = p; }
  
  IO() {
#ifdef EFILE
    Istream = fopen(EFILE ".in", "r");
    Ostream = fopen(EFILE ".out", "w");
#else
#ifdef _LOCAL
    Istream = fopen("input.txt", "r");
#endif
#endif
  }

  ~IO() { _flush(); }
} bin;
}
using _IO::bin;

// :/

struct Query {
  tp l, r, x, id;
};

tp n, m, l;

void STRUGGLING([[maybe_unused]] tp TEST_NUMBER) {
  bin >> n >> m;
  vector<tp> a(n), b(n);
  vector<Query> q(m);
  vector<double> tar(m);
  vector<vector<double>> f(15, vector<double>(n));
  bin.precision(12);
  for (tp i = 0; i < n; ++i) bin >> a[i];
  for (tp i = 0; i < n; ++i) bin >> b[i];
  for (tp i = 0; i < m; ++i) bin >> q[i].l >> q[i].r >> q[i].x;
  for (tp i = 0; i < m; ++i) { --q[i].l; --q[i].r; q[i].id = i; }
  stable_sort(q.begin(), q.end(), [](Query a, Query b) { return a.x < b.x; });
  for (double h = 1; h <= 1000000; h *= 1.25) {
    for (tp i = 0; i < n; ++i) {
      double den = 1;
      for (tp j = 0; j < 15; ++j) {
        den *= b[i] + h;
        if (i) f[j][i] = f[j][i - 1] + (j & 1 ? -a[i] / den : a[i] / den);
        else f[j][i] = j & 1 ? -a[i] / den : a[i] / den;
      }
    }
    while (l < m && q[l].x >= h && q[l].x < h * 1.25) {
      double res = 0, px = 1;
      for (int i = 0; i < 15; ++i) {
        if (!q[l].l) res += px * f[i][q[l].r];
        else res += px * (f[i][q[l].r] - f[i][q[l].l - 1]);
        px *= q[l].x - h;
      }
      tar[q[l++].id] = res;
    }
  }
  for (auto& i : tar) bin << i << '\n';
}

void MIST() {
}

#include <fstream>

signed main() {
  tp t = 0, _t = 1;
  MIST();
#if _MULTI_TESTS
  bin >> _t;
#endif
  while (t < _t) STRUGGLING(++t);
  return 0;
}

//*/

暂无评论

发表评论