RXD and functions

题目链接

题意

已知$f(x)= \sum_{i=0}^{n} c_{i} {x}^{i}.$
定义变换$Tr(f,a)$，使得$g(x)=Tr(f,a)=f(x-a).$
已知$g_{0}=f$，且有$g_{i}=Tr(g_{i-1}, a_{i}),g_{m} = \sum_{i=0}^{n} b_{i} {x}^{i}$，输入$m$。
求$b_{i}$对$998244353$取模。

思路

推式子时间到。

$$f(x) = \sum_{i=0}^{n} c_{i} {x}^{i}$$ $$Tr(f, a)=f(x-a)$$ $$g_{0}=f, g_{i}=Tr(g_{i-1}, a_{i}).$$ $$g_{1}= \sum_{i=0}^{n} c_{i}{(x-a_{1})}^{i}.$$ $$g_{2}= \sum_{i=0}^{n} c_{i} {(x - a_{1} - a_{2})}^{i}.$$ $$...$$ $$g_{m} = \sum_{i=0}^{n} c_{i} {(x-a_{1}-a_{2}-a_{3}...)}^{i}.$$ $$S = \sum_{i=1}^{m} a_{i}.$$ $$g_{m} = \sum_{i=0}^{n} c_{i} {(x-S)}^{i}.$$ $$=b_{i}{x}^{i}.$$ $$b_{i} = \sum_{j=i}^{n}c_{j} C_{j}^{i} {(-S)}^{j-i}.$$ $$= \sum_{j=i}^{n} c_{j} \times \frac{j!}{(j-i)!i!} {(-S)}^{j-i}.$$ $$= \frac{1}{i!} \sum_{j=i}^{n} c_{j} \frac{j!}{(j-i)!} {(-S)}^{j-i}.$$ $$= \frac{1}{i!} \sum_{j=0}^{n-i} c_{i+j} (i+j)! \frac{ {(-S)}^{j} }{j!}.$$ $$= \frac{1}{i!} \sum_{j=0}^{n-i} c_{i+j} (i+j)! \frac{ {(-S)}^{n-(n-j)} }{(n-(n-j))!}.$$ $$= \frac{1}{i!} \times (A*B)_{n+i}.$$

其中$A_{i} = c_{i} \times i!,B_{i} = \frac{ {(-S)}^{n-i} }{(n-i)!}.$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50

const ll mod = 998244353;
const ll g = 3;
ll Pow(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

void change(ll y[],int len)
{
    for(int i = 1, j = len / 2; i < len - 1; i++)
    {
        if (i < j)
			swap(y[i], y[j]);
        int k = len / 2;
        while (j >= k)
        {
            j -= k;
            k /= 2;
        }
        if (j < k)
			j += k;
    }
}
void ntt(ll y[], int len, int on)
{
    change(y, len);
    for(int h = 2; h <= len; h <<= 1)
    {
        ll wn = Pow(g, (mod-1) / h);
        if(on == -1)
			wn = Pow(wn, mod-2);
        for(int j = 0; j < len; j += h)
        {
            ll w = 1LL;
            for (int k = j; k < j + h / 2; k++)
            {
                ll u = y[k];
                ll t = w * y[k + h / 2] % mod;
                y[k] = (u + t) % mod;
                y[k + h / 2] = (u - t + mod) % mod;
                w = w * wn % mod;
            }
        }
    }
    if (on == -1)
    {
        ll t = Pow(len, mod-2);
        for(int i = 0; i < len; i++)
            y[i] = y[i] * t % mod;
    }
}
const int N = 1e5 + 5;
ll c[N], b[N];
ll x1[N << 2], x2[N << 2];
ll fac[N], inv[N];
int main()
{
	ll n, m;
	fac[0] = 1;
	for (int i = 1; i <= 100000; i++)
		fac[i] = fac[i - 1] * i % mod;
	inv[100000] = Pow(fac[100000], mod - 2);
	for (int i = 99999; i >= 0; i--)
		inv[i] = inv[i + 1] * (i + 1) % mod;
	while (scanf("%lld", &n) != EOF)
	{
		for (int i = 0; i <= n; i++)
			scanf("%lld", &c[i]);
		ll s = 0;
		scanf("%lld", &m);
		for (int i = 1; i <= m; i++)
		{
			ll a;
			scanf("%lld", &a);
			s = (s + a + mod) % mod;
		}
		if (s == 0)
		{
			for (int i = 0; i <= n; i++)
				printf("%lld ", c[i]);
			putchar('\n');
			continue;
		}
		int len = 1;
		while (len <= 2 * (n + 1))
			len <<= 1;
		for (int i = 0; i <= len; i++)
			x1[i] = x2[i] = 0;
		for (int i = 0; i <= n; i++)
			x1[i] = c[i] * fac[i] % mod;
		ll tmp = 1ll;
		for (int i = n; i >=0; i--)
		{
			x2[i] = tmp * inv[n - i] % mod;
			tmp = tmp * (-s) % mod;
			tmp = (tmp + mod) % mod;
		}
		ntt(x1, len, 1);
		ntt(x2, len, 1);
		for (int i = 0; i < len; i++)
			x1[i] = x1[i] * x2[i] % mod;
		ntt(x1, len, -1);
		for (int i = n; i <= 2 * n; i++)
			printf("%lld ", x1[i] * inv[i - n] % mod);
		putchar('\n');
	}
	return 0;
}