P5394 【模板】下降幂多项式乘法

(Updated: )
(7 mins to read)

下降幂多项式：Falling Factorial Polynomial(FFP)形式$f(x) = \sum \limits_{i=0}^{n}a_ix^{\underline{i}}$普通多项式与下降幂多项式是一一对应的（从高幂次向低幂次配系数即可）现在给出两个下降幂多项式f，g，要求出这两个多项式乘法的结果（输出普通多项式的系数）$n \leq 10^5$在FFT下，普通多项式在单位根处的点值可以快速计算而下降幂多项式在$0 \dots n$处的点值可以快速计算考虑f(x)的EGF：$\sum\limits_{i=0}^{\infty} \frac{f(i)}{i!}x^i = \sum \limits_{i=0}^{\infty}\frac{\sum \limits_{j=0}^{n} a_ji^{\underline{j}}}{i!}x^i = \sum\limits_{j=0}^n a_j \sum\limits_{i=0}^\infty \frac{1}{(i-j)!}x^i =\sum\limits_{j=0}^n a_jx^j \sum\limits_{i=0}^\infty \frac{x^i}{i!} =e^x\sum\limits_{i=0}^na_ix^i$所以我们只要把下降幂多项式当成普通多项式，然后卷上一个$e^x$就可以快速计算出f(x)在$0\dots n$处的取值（实质是$\frac{f(x)}{x!}$​）那么将f和g分别卷上$e^x$然后对应点值相乘，再反变换回去（乘上$e^{-x} =\sum\limits_{i=0}^\infty \frac{(-x)^i}{i!}$​）即可复杂度$O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
const int N = 8e5 + 5;
const int mod = 998244353, G = 3;
int up, w[N], rev[N], fac[N], ifac[N];
int fpw(int a, int b)
{
  int ans = 1;
  while(b)
  {
    if(b&1) ans = 1ll*ans*a%mod;
    a = 1ll*a*a%mod;
    b >>= 1;
  }
  return ans;
}
namespace poly
{
  void init(int n)
  {
    up = 1; int l = 0;
    while(up<=n) up <<= 1, l++;
    for(int i=0; i<up; i++) rev[i] = (rev[i>>1]>>1)|((i&1)<<(l-1));
    int wn = fpw(G, mod>>l); w[up>>1] = 1;
    for(int i=(up>>1)+1; i<up; i++) w[i] = 1ll*w[i-1]*wn%mod;
    for(int i=(up>>1)-1; i>=1; i--) w[i] = w[i<<1];
  }
  void clear(int *a, int n) { memset(a, 0, n<<2); }
  int getlen(int n) { return 1<<(32-__builtin_clz(n)); }
  inline void mul(int *a, int n, int x, int *b) { while(n--) *b++ = 1ll**a++*x%mod; }
  inline void dot(int *a, int *b, int n, int *c) { while(n--) *c++ = 1ll**a++**b++%mod; }
  void DFT(int *a, int l)
  {
    static unsigned long long tmp[N];
    int u = __builtin_ctz(up/l), t;
    for(int i=0; i<l; i++) tmp[i] = a[rev[i]>>u];
    for(int i=1; i^l; i<<=1)
      for(int j=0, d=i<<1; j^l; j+=d)
        for(int k=0; k<i; k++)
          t = tmp[i|j|k]*w[i|k]%mod, tmp[i|j|k] = tmp[j|k]+mod-t, tmp[j|k] += t;
    for(int i=0; i<l; i++) a[i] = tmp[i]%mod;
  }
  void IDFT(int *a, int l)
  {
    reverse(a+1, a+l); DFT(a, l);
    mul(a, l, mod-mod/l, a);
  }
  inline void conv(int *a, int *b, int l) { DFT(a, l); DFT(b, l); dot(a, b, l, a); IDFT(a, l); }
}
int n, m, a[N], b[N];
void ffp(int *a, int n, int op)
{
  static int tmp[N];
  poly::clear(tmp, up);
  if(op) for(int i=0; i<=n; i++) tmp[i] = ifac[i];
  else for(int i=0; i<=n; i++) if(i&1) tmp[i] = mod - ifac[i]; else tmp[i] = ifac[i];
  poly::conv(a, tmp, up);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  int deg = n + m;
  fac[0] = 1;
  for(int i=1; i<=deg; i++) fac[i] = 1ll*fac[i-1]*i%mod;
  ifac[deg] = fpw(fac[deg], mod-2);
  for(int i=deg-1; i>=0; i--) ifac[i] = 1ll*ifac[i+1]*(i+1)%mod;
  poly::init(deg<<1);
  for(int i=0; i<=n; i++) cin >> a[i];
  for(int i=0; i<=m; i++) cin >> b[i];
  ffp(a, deg, 1); ffp(b, deg, 1);
  for(int i=0; i<up; i++) a[i] = 1ll*a[i]*b[i]%mod*fac[i]%mod;
  ffp(a, deg, 0);
  for(int i=0; i<=deg; i++) cout << a[i] << " \n"[i==deg];
  return 0;
}

那么这玩意除了做这种没啥用的模板题还能干啥呢