Luogu5349 幂

题面

题解

首先考虑对于一个单项式怎么做，多项式就是单项式的答案的和。

就求一下\(\mathbf f(n) = n^k\)吧。（下面设\(t = \dfrac 1r\)）

设\(\mathbf S_k = \sum_{n=0}^\infty n^k \left(\dfrac 1t\right)^n\)

\(t\mathbf S_k = \sum_{n=1}^\infty n^k \left(\dfrac 1t\right)^{n-1} = \sum_{n=0}^\infty (n+1)^k \left(\dfrac 1t\right)^n\)

所以\((t - 1) \mathbf S_k = \sum_{n=0}^\infty [(n+1)^k - n^k]\left(\dfrac 1t\right)^n\)

将\((n+1)^k\)用二项式定理展开可以发现：

\(\mathbf S_k = \dfrac 1{t-1} \sum_{i=0}^{k-1} \binom ki \mathbf S(i), \mathbf S_0 = \dfrac t{t-1}\)

于是\(\mathbf S_{k} = \dfrac {k!}{t-1}\sum_{i=0}^{k-1} \dfrac 1{(k - i)!} \dfrac {\mathbf S(i)}{i!}\)

显然卷积的形式，分治\(\mathrm{FFT}\)即可。

代码

我不会告诉你我是直接蒯的分治FFT的代码

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#define RG register

#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);

#define clear(x, y) memset(x, y, sizeof(x))

inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while(ch != '-' && (!isdigit(ch))) ch = getchar();

	if(ch == '-') w = -1, ch = getchar();

	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}

const int Mod(998244353), G(3), maxn(3e5 + 10), phi(Mod - 1);

inline int fastpow(int x, int y)

{

	int ans = 1;

	while(y)

	{

		if(y & 1) ans = 1ll * ans * x % Mod;

		x = 1ll * x * x % Mod, y >>= 1;

	}

	return ans;

}

inline int Inv(int x) { return fastpow(x, Mod - 2); }

int r[maxn], N, m, f[maxn], g[maxn], fac[maxn], inv[maxn], invk;

template<int opt> void FFT(int *p)

{

	for(RG int i = 0; i < N; i++) if(i < r[i]) std::swap(p[i], p[r[i]]);

	for(RG int i = 1; i < N; i <<= 1)

	{

		int rot = fastpow(G, phi / (i << 1));

		for(RG int j = 0; j < N; j += (i << 1))

		{

			int w = 1;

			for(RG int k = 0; k < i; ++k, w = 1ll * w * rot % Mod)

			{

				int x = p[j + k], y = 1ll * w * p[i + j + k] % Mod;

				p[j + k] = (x + y) % Mod, p[i + j + k] = (x - y + Mod) % Mod;

			}

		}

	}

	if(opt == -1) std::reverse(p + 1, p + N);

}

void Div(int l, int r)

{

	static int a[maxn], b[maxn], P;

	if(r - l <= 1) return;

	int mid = (l + r) >> 1;

	Div(l, mid);

	for(m = r - l, N = 1, P = -1; N <= m; N <<= 1, ++P);

	int invn = Inv(N);

	for(RG int i = 0; i < N; i++)

		::r[i] = (::r[i >> 1] >> 1) | ((i & 1) << P);

	std::copy(f + l, f + mid, a); std::fill(a + mid - l, a + N, 0);

	for(RG int i = 0; i < mid - l; i++) a[i] = 1ll * a[i] * inv[i + l] % Mod;

	std::copy(inv, inv + r - l, b); std::fill(b + r - l, b + N, 0);

	FFT<1>(a), FFT<1>(b);

	for(RG int i = 0; i < N; i++) a[i] = 1ll * a[i] * b[i] % Mod;

	FFT<-1>(a);

	for(RG int i = mid; i < r; i++)

		f[i] = (f[i] + 1ll * fac[i] * a[i - l] % Mod * invk % Mod * invn % Mod) % Mod;

	Div(mid, r);

}

int n, k;

int main()

{

#ifndef ONLINE_JUDGE

	file(cpp);

#endif

	n = read() + 1, k = Inv(read()); invk = Inv(k - 1); fac[0] = inv[0] = 1;

	for(RG int i = 1; i <= n + n; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;

	inv[n + n] = Inv(fac[n + n]);

	for(RG int i = n + n - 1; i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % Mod;

	f[0] = 1ll * k * invk % Mod; Div(0, n);

	int ans = 0;

	for(RG int i = 0; i < n; i++)

		ans = (ans + 1ll * read() * f[i] % Mod) % Mod;

	printf("%d\n", ans);

	return 0;

}

巴特西

Luogu5349 幂

题面

题解

代码

最新文章

热门文章