CodeChef Weird Product

2021/12/15 23:14:42

编程Tag： value return int product PROD limits mod Weird CodeChef

本文主要是介绍CodeChef Weird Product，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

CodeChef Weird Product

设 \(p_k=\sum\limits_{i=1}^kA_iX^i\)，且 \(p_0=0\)。则 \(\forall 1\le i\le j\le N,\,W(i,j)=\dfrac{p_j-p_{i-1}}{X^i}\)。于是有

\[\begin{align*}P&=\prod_{i=1}^N\prod_{j=i}^NW(i,j)^2\\&=\left(\prod_{i=0}^N\prod_{j=i+1}^N\dfrac{p_j-p_i}{X^{i+1}}\right)^2\\&=\dfrac{\left(\prod\limits_{i=0}^N\prod\limits_{j=i+1}^N(p_j-p_i)\right)^2}{X^{2\times \sum\limits_{i=1}^Ni\cdot(N-i)}}\end{align*} \]

上式中的分母很好计算，现在主要考虑如何计算分子。

注意到 \((p_j-p_i)^2=-(p_j-p_i)\cdot(p_i-p_j)\)，则可以考虑将分子变形为

\[\begin{align*}\operatorname{Numerator}(P)&=(-1)^{\frac{N\cdot(N+1)}{2}}\prod_{i=0}^{N}\prod_{j\neq i}(p_j-p_i)\end{align*} \]

设 \(f(i)=\prod\limits_{j\neq i}(p_i-p_j)\)，那么有

\[\begin{align*}\operatorname{Numerator}(P)&=(-1)^{\frac{N\cdot(N+1)}{2}}\prod_{i=0}^{N}(-1)^{N}f(i)\end{align*} \]

可以考虑直接将 \(f(0\ldots N-1)\) 求出来。

注意到 \(f(i)\) 的结构非常相似，因此我们的想法是找到一个多项式 \(F(x)\) 满足 \(f(i)=F(p_i)\)。如果找到了这样的 \(F(x)\)，那么就可以对 \(F(x)\) 做一遍多项式多点求值来求出 \(f(i)\)。

于是我们可以考虑类似于拉格朗日插值定理那样的方式去构造：设 \(F(x)=\sum\limits_{i=0}^N\prod\limits_{j\neq i}(x-p_j)\)，则有等式 \(F(p_i)=\prod\limits_{j\neq i}(p_i-p_j)=f(i)\)。那么又该如何将 \(F(x)\) 求出来呢？

让我们先考虑另一个多项式 \(G(x)=\prod\limits_{i=0}^N(x-p_i)\)。那么就有 \(F(x)=\sum\limits_{i=0}^N\dfrac{G(x)}{x-p_i}=G'(x)\)。于是只要将 \(G(x)\) 求出来再对其求导就行了。

至于如何求 \(G(x)\) 可以用启发式合并+NTT的方法，时间复杂度为 \(\mathcal O(N\log ^2N)\)；对 \(F(x)\) 进行多项式多点求值的时间复杂度也是 \(\mathcal O(N\log ^2N)\) 的。总时间复杂度就是线对平方。

参考代码

#include <bits/stdc++.h>
using namespace std;

/**
此处省略多项式全家桶的模板
**/

static constexpr value_t mod = poly::P;
inline value_t add(value_t x, value_t y) { return (x += y) >= mod ? x - mod : x; }
inline value_t mul(value_t x, value_t y) { return (int64_t)x * y % mod; }
inline value_t &add_eq(value_t &x, value_t y) { return x = add(x, y); }
inline value_t &mul_eq(value_t &x, value_t y) { return x = mul(x, y); }
inline value_t qpow(value_t x, int64_t y) {
  value_t r = 1;
  for (; y; y >>= 1, mul_eq(x, x))
    (y & 1) && (mul_eq(r, x));
  return r;
} // qpow

static constexpr int Maxn = 1e5 + 5;
int N;
value_t X, iX, Xp, A[Maxn];
value_t p[Maxn], P;
poly getG(int l, int r) {
  if (l == r) return poly{!p[l] ? 0 : mod - p[l], 1};
  int mid = (l + r) >> 1;
  return getG(l, mid) * getG(mid + 1, r);
} // getG
int main(void) {
  int tests;
  scanf("%d", &tests);
  while (tests--) {
    scanf("%d%u", &N, &X);
    p[0] = 0; Xp = 1;
    iX = qpow(X, mod - 2);
    for (int i = 1; i <= N; ++i) {
      scanf("%u", &A[i]);
      p[i] = add(p[i - 1], mul(A[i], mul_eq(Xp, X)));
    }
    auto f = getG(0, N).derivative().evaluate(vector(p, p + N + 1));
    bool neg = (((int64_t)N * (N + 1) / 2) % 2 == 1);
    value_t num = 1;
    for (int i = 0; i <= N; ++i) mul_eq(num, f[i]);
    int64_t Exp = (int64_t)N * (N + 1) * (N + 2) / 3;
    Exp %= (mod - 1);
    value_t dinom = qpow(iX, Exp);
    P = mul_eq(num, dinom);
    printf("%u\n", neg ? (!P ? 0 : mod - P) : P);
  }
  exit(EXIT_SUCCESS);
} // main

这篇关于CodeChef Weird Product的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

CodeChef Weird Product

CodeChef Weird Product

相关编程文章