自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:56:33，当前版本为作者最后更新于2024-03-17 09:07:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd on 2024.7.31：做法太唐，重写。

根据 简单版 的柿子，我们要计算下面这个东西：

$$\forall 0\le i\le n,[x^i]G(F+1)^i$$

先 $F\gets F+1$。考虑引入第二元 $y$ 用于区分不同的 $i$。我们只需要求出：

$$\begin{aligned} &[x^0]\sum_iy^iGF^ix^{-i}\\ \overset{\operatorname{rev}}{=}&[x^n]G\sum y^iF^{n-i}x^i\\ =&[x^n]GF^n\sum y^i(xF^{-1})^i\\ =&[x^n]\frac{GF^n}{1-yxF^{-1}}\\ \end{aligned} $$

直接 bostan-mori 计算，时间复杂度 $O(n\log^2 n)$。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 998244353;

using namespace polynomial; // By R_i.

typedef vector<poly<int>> polyv;

inline 
polyv operator * (const polyv &f, const polyv &g) {
	int n = f.size(), m = g.size(), x = f[0].size(), y = g[0].size();
	poly<int> a(n * (x + y - 1)), b(m * (x + y - 1));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < x; j++) a[i * (x + y - 1) + j] = f[i][j];
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < y; j++) b[i * (x + y - 1) + j] = g[i][j];
	}
	a *= b; polyv res(n + m - 1, poly<int>(x + y - 1));
	for (int i = 0; i < n + m - 1; i++) {
		for (int j = 0; j < x + y - 1; j++) res[i][j] = a[i * (x + y - 1) + j];
	}
	return res;
}

poly<int> bostan_mori(int n, polyv f, polyv g) {
	if (!n) return f[0] * inv(g[0]);
	if (n + 1 < f.size()) f.resize(n + 1);
	if (n + 1 < g.size()) g.resize(n + 1);
	polyv h = g;
	for (int i = 1; i < h.size(); i += 2) h[i] = -h[i];
	f = f * h, g = g * h; polyv a, b;
	for(int i = n & 1; i < f.size(); i += 2) a.push_back(f[i]);
	for(int i = 0; i < g.size(); i += 2) b.push_back(g[i]);
	return bostan_mori(n >> 1, a, b);
}

const int MAXN = 1e5 + 10;

int fac[MAXN], ifac[MAXN], tk[MAXN], p2[MAXN];

inline 
void init(int n) {
	*fac = 1;
	for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n; i; i--) ifac[i - 1] = (ll)ifac[i] * i % mod;
	tk[1] = 1;
	for (int i = 2; i <= n; i++) tk[i] = qpow(i, i - 2);
	*p2 = 1;
	for (int i = 1; i <= n; i++) p2[i] = (p2[i - 1] << 1) % mod;
}

int n, k, ans, t = 1, a[MAXN];

poly<int> f, g; polyv p, q;

int main() {
	scanf("%d%d", &n, &k), ++n, init(n), f.resize(n), g.resize(n);
	for (int i = 0; i < n; i++) g[i] = (ll)t * ifac[i] % mod, t = (ll)t * p2[i + 2 - k] % mod;
	for (int i = 0; i < n; i++) f[i] = (ll)tk[i] * ifac[i] % mod;
	g *= inv(exp(f)), g.resize(n), f[0]++;
	g = g * pow(f, n - 1), f = inv(f) >> 1;
	for (int i = 0; i < n; i++) {
		p.push_back(vector<int>({ g[i], 0 }));
		q.push_back(vector<int>({ !i, mod - f[i] }));
	}
	g = bostan_mori(n - 1, p, q), g.resize(n), g.reverse();
	for (int i = 0; i < n; i++) g[i] = (ll)g[i] * fac[i] % mod;
	for (int i = 0; i < n; i++) scanf("%d", &a[i]), ans = (ans + (ll)a[i] * g[i] % mod) % mod;
	printf("%lld", ans);
}