牛客 导一导 莱布尼茨求导公式

(Updated: )
(7 mins to read)

求$\sum\limits_{i=1}^k a_i\frac{sinx}{x^i}^{(n)}$输出$\frac{sinx}{x^i}$ 和$\frac{cosx}{x^i}$​前的系数$n, k \leq 10^5$

$(uv)^{(n)} = \sum\limits_{k=0}^n \binom{n}{k}u^{(k)}v^{(n-k)}$$\sum\limits_{j=0}^k \binom{k}{j} sinx^{(k-j)}\sum\limits_{i=1}^k(a_ix^{-i})^{(j)}$发现是一个多项式乘法的形式，继续化简$\sum\limits_{j=0}^k \binom{k}{j}sinx^{(k-j)}\sum\limits_{i=1}^ka_i(-i)^{\underline{j}}x^{-i-j}$$\sum\limits_{j=0}^k\binom{k}{j} sinx^{(k-j)}x^{-j}(-1)^j\sum\limits_{i=1}^ka_i\frac{(i+j-1)!}{(i-1)!}x^{-i}$把$(i+j-1)!$提出来，其余的就是两个多项式，NTT相乘后，最后再乘上$(i+j-1)!$的贡献即可

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
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, k, fac[N], ifac[N], a[N], b[N], bb[N], c[N];
const int mod = 998244353, G = 3;
int up, w[N], rev[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);
  }
}
int comb(int n, int m)
{
  if(n<m||n<0||m<0) return 0;
  return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  poly::init(n+k);
  fac[0] = 1;
  for(int i=1; i<=n+k; i++) fac[i] = 1ll*fac[i-1]*i%mod;
  ifac[n+k] = fpw(fac[n+k], mod-2);
  for(int i=n+k-1; i>=0; i--) ifac[i] = 1ll*ifac[i+1]*(i+1)%mod;
  for(int i=1; i<=k; i++)
  {
    cin >> a[i];
    a[i] = 1ll*a[i]*ifac[i-1]%mod;
  }
  poly::DFT(a, up);
  for(int i=0; i<=n; i++)
  {
    b[i] = comb(n, i);
    if((n-i)%4>1) b[i] = mod - b[i];
    if(i&1) b[i] = mod - b[i];
  }
  for(int i=0; i<=n; i+=2) bb[i] = b[i];
  poly::DFT(bb, up);
  for(int i=0; i<up; i++) c[i] = 1ll*a[i]*bb[i]%mod;
  poly::IDFT(c, up);
  for(int i=1; i<=n+k; i++) cout << 1ll*c[i]*fac[i-1]%mod << " \n"[i==n+k];

  poly::clear(bb, up);
  for(int i=1; i<=n; i+=2) bb[i] = b[i];
  poly::DFT(bb, up);
  for(int i=0; i<up; i++) c[i] = 1ll*a[i]*bb[i]%mod;
  poly::IDFT(c, up);
  for(int i=1; i<=n+k; i++) cout << 1ll*c[i]*fac[i-1]%mod << " \n"[i==n+k];
  return 0;
}