标签归档:拉格朗日插值法

2018牛客暑期ACM多校训练营(第一场)题解

A. Monotonic Matrix

给定$1\leq m,n \leq 1000$,求满足下列条件的$m \times n$矩阵个数,使得

  • $a_{i,j} \in \{0, 1, 2\}$
  • 每一行从左到右和每一列从上到下单调不减

题解:考虑每一行大于等于1和大于等于2的位置,其实就是要求两个单调不减的数列$\{a_i\}, \{b_i\}$的个数,满足对于任意$i$,有$a_i \leq b_i$。

B. Symmetric Matrix

给定$1 \leq n \leq 10^5$,求满足每个元素为非负整数,主对角线全0,每一行和为2的$n \times n$的对称矩阵的数量。

题解:把矩阵想象成邻接矩阵,就是要求顶点带标号的所有不允许自环、但允许重边的2-正则图的数量。

C. Fluorescent 2

在模2域下,给定$m \times n$的01矩阵$M$,$1 \leq n \leq 50$,$1 \leq m \leq 1000$,求对于每一个$n$维向量$v$,$Mv$中0的个数的三次方的和。

D. Two Graphs

给定图$G_1 = (V, E_1), G_2 = (V, E_2)$,求有多少$E_1$的子集$E’$,使得$(V, E’)$与$G_2$同构。点数不超过8。

题解:枚举所有的排列,如果构成子图,就把选出来的边用bitmap表示出来,最后去重即可。

E. Removal

给定$1 \leq n \leq 10^5$个数的序列,每个数为不超过$k$的正整数。问删掉$m$个数后,有多少种不同的子序列。$k, m$不超过10。

题解:用dp[i][j][k]表示前i个数删去j个数后,最后一个数为k的方案数。可以在$O(1)$时间内转移。

F. Sum of Maximum

给定数列$a_1, a_2, \cdots, a_n$,求

\[\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}\]

题解:把$\max\{x_1, x_2, \cdots, x_n\}$写为$\sum_{m=1}^a [\exists i, x_i \geq m]$,进而改写为$\sum_{m=1}^a 1-[\forall i, x_i < m]$。将$a_i$排序后,从大到小分段计算,每一段都是$x_i$的一个前缀积乘以$i^k$的求和,后者可用Lagrange插值法快速计算。

G. Steiner Tree

H. Longest Path

I. Substring

给一个字符集为{a,b,c}的字符串,求在同构意义下的子串的等价类的数目。两个串同构当且仅当长度相等,并且存在字符集到字符集的双射f,使得一个串经过f变换后变成另一个串。

题解:将原串经过6种双射f后变成的6个串丢到SAM里,求出所有本质不同的子串。含有大于等于2种子串有6中不同的同构串,而只含有1种字符的串只有3中不同的同构串,分类讨论一下即可。

J. Different Integers

给一个序列,每次询问给出一个区间,求序列扣除这个区间后,有多少个不同数。

题解:在某次询问中,某数不出现当且仅当这个数第一次出现到最后一次出现包含于询问区间中即可。只要离线排序一下,按右端点的顺序处理即可。

k次幂前缀和的线性做法

给定正整数 $x, k$ 和质数 $p$,求
\[ \sum_{i=1}^{x} i^k \bmod p \]

这是一道很经典的题目,在杜瑜皓的《多项式及求和》中有详细讨论。比较暴力的做法是对于每个 $i^k$ 都用快速幂算出其值,然后相加,时间复杂度为 $O(x \log k) $,当 $x$ 很大时,就超时了。然而利用拉格朗日插值法,这题最快可以做到 $O(k)$ 的复杂度,其做法主要由以下几部分构成。

线性预处理逆元

求 1..n 之间每个数的逆元,如果都用费马小定理或者扩展欧几里得算,那么复杂度将会达到 $O(n \log p)$ 或 $O(n \log n)$。利用一些递推式,可以线性地求出 1..n 中每个数的逆元,从而复杂度可以减少一个 log。常用的一个递推公式是

\[ i^{-1} = -\left\lfloor \frac{p}{i} \right\rfloor \cdot (p \bmod i)^{-1} \bmod p \]

这一公式的正确性也很好证明,等式右端可以写成

\[ -\frac{\left\lfloor \frac{p}{i} \right\rfloor}{p-\left\lfloor \frac{p}{i} \right\rfloor i} = \frac{1}{i} \]

利用此公式,可以在 $O(n)$ 时间内求出 1..n 中每一个数的逆元。

线性筛求积性函数的值

注意到 $i^k$ 是一个积性函数,这样,利用线性筛,我们只需要用快速幂计算素数 $i$ 的值,其他点的函数值就可以直接得到。根据素数定理,前 $n$ 个数中素数的个数约为 $O(\frac{n}{\log n})$,从而利用快速幂计算出素数处的值,可以做到 $O(\frac{n}{\log n}\log{k}$ ,再加上筛法本身 $O(n)$ 的复杂度,我们可以在 $O(n + \frac{n}{\log n}\log{k})$ 的时间复杂度内计算出 $i^k$ 的前 $n$ 项值。

拉格朗日插值法

注意到答案一定是关于 $x$ 的 $k+1$ 次多项式。而根据线性代数的知识,我们只要知道这个多项式的任意 $k+2$ 个点处的值,我们就能确定这个多项式。拉格朗日插值公式就给出了这个多项式

\[ f(x) = \sum_{i=0}^{k+1} y_i l_i(x) \]

其中

\[ l_i(x) = \prod_{0 \leq m \leq k+1, m \neq i} \frac{x – x_m}{x_j – x_m} \]

具体到这道题上,插值公式就是

\[ f(n) = \sum_{i = 0}^{k+1} (-1)^{k+i+1} f(i) \frac{n(n-1) \cdots (n-i+1)(n-i-1) \cdots (n-d)}{(d-i)!i!} \]

其中 $f(i)$ 就是 $i^k$ 的前缀和,上式右端求和的每一项,分子都是 n 到 n-d 的前缀积乘后缀积,分母可以用递推线性求出,这样就可以在 $O(k)$ 时间内解决整个问题。

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

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

#define pow owahgrauhgso

ULL n, k, m;

ULL powmod(ULL b, ULL e) {
  ULL r = 1;
  while (e) {
    if (e & 1) r = r * b % m;
    b = b * b % m;
    e >>= 1;
  }
  return r;
}

const int MAXN = 1000006;
ULL inv[MAXN];

void init_inv() {
  inv[1] = 1;
  for (int i = 2; i <= k+1; i++) { 
    inv[i] = (m - m / i) * inv[m % i] % m; 
    assert(inv[i] * i % m == 1);
  }
}

ULL pow[MAXN];
ULL prime[MAXN], cnt;

void sieve() {
  pow[1] = 1;
  for (int i = 2; i <= k+1; i++) {
    if (!pow[i]) {
      pow[i] = powmod(i, k);
      prime[cnt++] = i;
      for (int j = 0; j < cnt && i*prime[j] <= k+1; j++) {
        pow[i * prime[j]] = pow[i] * pow[prime[j]] % m;
        if (i % prime[j] == 0) break;
      }
    }
  }
}

ULL sum[MAXN];
ULL ans[MAXN];

auto addmod = [](ULL a, ULL b) -> ULL {return (a+b)%m;};

ULL lagrange() {
  ULL p;
  p = 1;
  for (int i=0; i<=k+1; i++) {
    if (i) p = p * inv[i] % m;
    ans[i] = (k+1-i)&1 ? m-sum[i] : sum[i];
    ans[i] = ans[i] * p % m;
    p = p * (m + n - i) % m;
  }
  p = 1;
  for (int i=k+1; i>=0; i--) {
    if (k+1-i) p = p * inv[k+1-i] % m;
    ans[i] = ans[i] * p % m;
    p = p * (m + n - i) % m;
  }
  return accumulate(ans, ans+k+2, 0, addmod); 
}

int main() { 
  cin >> n >> k >> m; 
  init_inv(); sieve(); 
  partial_sum(pow, pow+k+2, sum, addmod);  
  cout << lagrange() << endl; 
 return 0; 
}