导数卷积

题目描述

题解

参考了一下标程的推导过程,因为这个推导对我这种数学弱渣真的有点难鸭.

[1]$f(x)$f(x)的$i$i次导函数:

$f^{(i)}(x) = a_{i}*\frac{i!}{0!} + a_{i+1}*\frac{(i+1)!}{1!}*x^{1} +...+a_{n-1}*\frac{(n-1)!}{(n-1-i)!}*x^{n-1-i}$f(i)(x)=ai​∗0!i!​+ai+1​∗1!(i+1)!​∗x1+...+an−1​∗(n−1−i)!(n−1)!​∗xn−1−i

[2]$f(x)$f(x)的$n-i-1$n−i−1次导函数:

$f^{(n-i-1)}(x) = a_{n-i-1}*\frac{(n-1-i)!}{0!} + a_{n-i}*\frac{(n-i)!}{1!}*x^{1} +...+a_{n-1}*\frac{(n-1)!}{i!}*x^{i}$f(n−i−1)(x)=an−i−1​∗0!(n−1−i)!​+an−i​∗1!(n−i)!​∗x1+...+an−1​∗i!(n−1)!​∗xi

对于积式$f^{(i)}(x)f^{(n-1-i)}(x)$f(i)(x)f(n−1−i)(x)结果中,次数为$d$d的项$x^d$xd前的系数应该是:

$\sum_{t = 0}^{d}a_{i+t}*\frac{(i+t)!}{t!}*a_{n-i-1+(d-t)}*\frac{(n-i-1+(d-t))!}{(d-t)!}$∑t=0d​ai+t​∗t!(i+t)!​∗an−i−1+(d−t)​∗(d−t)!(n−i−1+(d−t))!​

令$F_i = a_i * i!$Fi​=ai​∗i!

换种写法:

$\sum_{t = 0}^{d}F_{i+t}*\frac{1}{t!}*F_{n-1+d-(i+t)}*\frac{1}{(d-t)!}$∑t=0d​Fi+t​∗t!1​∗Fn−1+d−(i+t)​∗(d−t)!1​

对所有的积式求和得到:

$\sum_{i= 0}^{n-1}\sum_{t = 0}^{d}F_{i+t}*\frac{1}{t!}*F_{n-1+d-(i+t)}*\frac{1}{(d-t)!}$∑i=0n−1​∑t=0d​Fi+t​∗t!1​∗Fn−1+d−(i+t)​∗(d−t)!1​

$=\sum^{n-1+d}_{i=0}F_{i}*F_{n-1+d-i}*\sum^{d}_{j=0}\frac{1}{j!(d-j)!}$=∑i=0n−1+d​Fi​∗Fn−1+d−i​∗∑j=0d​j!(d−j)!1​

在上个式子中必须要满足$n-1+d-i \le n-1$n−1+d−i≤n−1, 即,$d \le i$d≤i ,不然$F_{n-1+d-i}$Fn−1+d−i​将变成$0$0,不过对答案没有影响.

$j$j的取值范围是$j:[0,min(d,i)]$j:[0,min(d,i)],也就是$j:[0,d]$j:[0,d].

因此上个式子就是,

$=\sum^{n-1+d}_{i=0}F_{i}*F_{n-1+d-i}*\frac{2^d}{d!} = \frac{2^d}{d!} *\sum^{n-1+d}_{i=0}F_{i}*F_{n-1+d-i}$=∑i=0n−1+d​Fi​∗Fn−1+d−i​∗d!2d​=d!2d​∗∑i=0n−1+d​Fi​∗Fn−1+d−i​

对后面的部分$\sum^{n-1+d}_{i=0}F_{i}*F_{n-1+d-i}$∑i=0n−1+d​Fi​∗Fn−1+d−i​直接套用$NTT$NTT来求就可以了.

代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
#define rep(i,a,b) for(int i = a;i <= b;++i)
typedef long long LL;
const int N = 1 << 20;
const int P = 998244353;
const int G = 3;
const int NUM = 20;

LL  wn[NUM];
LL  a[N], b[N];

LL quick_mod(LL a, LL b, LL m)
{
    LL ans = 1;
    a %= m;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % m;
            b--;
        }
        b >>= 1;
        a = a * a % m;
    }
    return ans;
}

void GetWn()
{
    for(int i = 0; i < NUM; i++)
    {
        int t = 1 << i;
        wn[i] = quick_mod(G, (P - 1) / t, P);
    }
}
void Rader(LL a[], int len)
{
    int j = len >> 1;
    for(int i = 1; i < len - 1; i++)
    {
        if(i < j) swap(a[i], a[j]);
        int k = len >> 1;
        while(j >= k)
        {
            j -= k;
            k >>= 1;
        }
        if(j < k) j += k;
    }
}

void NTT(LL a[], int len, int on)
{
    Rader(a, len);
    int id = 0;
    for(int h = 2; h <= len; h <<= 1)
    {
        id++;
        for(int j = 0; j < len; j += h)
        {
            LL w = 1;
            for(int k = j; k < j + h / 2; k++)
            {
                LL u = a[k] % P;
                LL t = w * a[k + h / 2] % P;
                a[k] = (u + t) % P;
                a[k + h / 2] = (u - t + P) % P;
                w = w * wn[id] % P;
            }
        }
    }
    if(on == -1)
    {
        for(int i = 1; i < len / 2; i++)
            swap(a[i], a[len - i]);
        LL inv = quick_mod(len, P - 2, P);
        for(int i = 0; i < len; i++)
            a[i] = a[i] * inv % P;
    }
}

void Conv(LL a[], LL b[], int n)
{
    NTT(a, n, 1);
    NTT(b, n, 1);
    for(int i = 0; i < n; i++)
        a[i] = a[i] * b[i] % P;
    NTT(a, n, -1);
}
int n;
LL Fac[N],iFac[N];
int main()
{
    GetWn();
	Fac[0] = 1;
	rep(i,1,N-1) 
		Fac[i] = Fac[i-1] * i % P;
	rep(i,0,N-1)
		iFac[i] = quick_mod(Fac[i],P-2,P);
	ios::sync_with_stdio(false);
	cin >> n;
	rep(i,0,n-1) {
		std::cin >> a[i];
		a[i] = b[i] = a[i] * Fac[i] % P;
	}
	int len = 1;
	while(len < n) len <<= 1;
    len <<= 1;
	Conv(a,b,len);
	rep(i,0,n-1) {
		std::cout << a[n-1+i] * quick_mod(2,i,P) % P * iFac[i] % P << " ";
	}
    return 0;
}