ARC134F Flipping Coins

pb 讲课没讲的题，感觉很牛逼啊！但不是牛逼在多项式，因为多项式大家应该都会。

考虑从前往后扫的过程，只要有正面就翻成反面，所以最后只有可能是当 \(p_i<i\) 且 \(i\) 没有被翻面时才对 \(k\) 有贡献。那么考虑一条链 \(1\to 2\to \cdots \to m\)，并且 \(\forall 1\le i< m,p_i=i+1\)，那么此时翻了 \(1\) 就会翻 \(2\)，翻了 \(3\) 就会翻 \(4\)……不难发现此时当且仅当 \(2\nmid m\) 才对 \(k\) 有 \(1\) 的贡献。

于是考虑把排列分成若干置换环，并单独考虑每一个环。不难发现，我们在每个置换环的最小值处断环成链，最后这个环对 \(k\) 的贡献就是这条链上正面朝上的硬币个数，就是这条链长度为奇数的极长上升子段个数。

把所有链按照最小值从大到小进行排序，然后排成一排变成排列 \(q\)。不难发现 \(p,q\) 是一一对应的，同时 \(p\) 对应的 \(k\) 就是 \(q\) 长度为奇数的极长上升子段个数。

接下来是一个很神仙的转化：把每个极长上升子段拆成 \(\mathtt{ABABAB\cdots C}\) 的形式，即分成若干长度为 \(2\) 和 \(1\) 的小段，长度为 \(2\) 的标为 \(\mathtt{AB}\)，长度为 \(1\) 的标为 \(\mathtt{C}\)，\(k\) 就是长为 \(1\) 的小段即 \(\mathtt{C}\) 的个数。

发现我们所需要满足的条件如下：

• 由于 \(\mathtt{ABABAB\cdots}\) 形如上升状子段，所以每个 \(\mathtt{A}\) 代表的数都比后面相邻的 \(\mathtt{B}\) 小。
• \(\mathtt{B}\) 是没有限制的，因为它可以作为长度为偶数的极长上升子段末尾，也可以在后面接上一个单独的一个 \(\mathtt{C}\)。
• 每个 \(\mathtt{C}\) 都要大于后面的数，不管是 \(\mathtt{A}\) 还是 \(\mathtt{C}\)，否则可以匹配成 \(\mathtt{AB}\)。

所以我们以每个 \(\mathtt{B}\) 为末尾断开，把序列分成形如 \((\mathtt{CC\cdots CAB})(\mathtt{CC\cdots CAB})(\mathtt{CC\cdots C})\) 的形式。

然后考虑生成函数，列出整个排列的 EGF \(F(x)\)，形如 \(\mathtt{CC\cdots CAB}\) 的 EGF \(G(x)=\sum\limits_{i=2}(i-1)w^{i-2}\dfrac{x_i}{i!}\)，形如 \(\mathtt{CC\cdots C}\) 的 EGF \(H(x)=\sum\limits_{i=0}w^i\dfrac{x^i}{i!}\)，然后显然有 \(F(x)=F(x)G(x)+H(x)\)，即 \(F(x)=\frac{H(x)}{1-G(x)}\)，求逆即可。

（为什么是 EGF 傻子都知道，不要再过来找我问了。）

当然直接推朴素的 dp 应该有一个可以分治 NTT 的形式，这个也能做，不过本质上其实就是 EGF 卷积。

然后找个板子过来就 \(O(n\log^2n)\) 或者 \(O(n\log n)\) 随便做了。

// Problem: F - Flipping Coins
// Contest: AtCoder - AtCoder Regular Contest 134
// URL: https://atcoder.jp/contests/arc134/tasks/arc134_f
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace vbzIO {
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
	#else
	#define gh() getchar()
	#endif
	#define mt make_tuple
	#define mp make_pair
	#define fi first
	#define se second
	#define pc putchar
	#define pb push_back
	#define ins insert
	#define era erase
	#define bg begin
	#define rbg rbegin
	typedef tuple<int, int, int> tu3;
	typedef pair<int, int> pi;
	inline int rd() {
		char ch = gh();
		int x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}
	inline void wr(int x) {
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		if (x > 9)
			wr(x / 10);
		putchar(x % 10 + '0');
	}
}
using namespace vbzIO;

const int N = 3e6 + 300;
const int P = 998244353;
const int g = 114514;

int n, w, tr[N];
int f[N], h[N], fac[N], inv[N], ifac[N];

int qpow(int p, int q) {
    int res = 1;
    while (q) {
        if (q & 1) res = res * p % P;
        p = p * p % P, q >>= 1;
    }
    return res;
}

void init(int lim) {
	fac[0] = ifac[0] = inv[1] = 1;
	for (int i = 1; i <= lim; i++) {
		if (i > 1) inv[i] = inv[P % i] * (P - P / i) % P;
		fac[i] = fac[i - 1] * i % P, ifac[i] = ifac[i - 1] * inv[i] % P;
	}
}

const int gi = qpow(g, P - 2);

void NTT(int *f, int lim, int op){
    for (int i = 0; i < lim; i++) 
        if (i < tr[i]) swap(f[i], f[tr[i]]);
    for (int o = 2, k = 1; k < lim; o <<= 1, k <<= 1) {
    	int tg = qpow(~op ? g : gi, (P - 1) / o);
    	for (int i = 0; i < lim; i += o) {
    		for (int j = 0, w = 1; j < k; j++, (w *= tg) %= P) {
    			int x = f[i + j];
    			int y = w * f[i + j + k] % P;
    			f[i + j] = (x + y) % P;
    			f[i + j + k] = (x - y + P) % P;
			}
		}
	}
	if (op == 1) return;
	int iv = qpow(lim, P - 2);
	for (int i = 0; i < lim; i++) 
		(f[i] *= iv) %= P;
}

void INV(int *f, int *g, int n) {
	if (n == 1) return g[0] = qpow(f[0], P - 2), void();
	INV(f, g, (n + 1) >> 1);
	static int t[N];
	int lim = 1, len = 0;
	while (lim < (n << 1)) lim <<= 1, len++;
    for (int i = 0; i < lim; i++) 
		tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (len - 1));
	for (int i = 0; i < n; i++) t[i] = f[i];
	for (int i = n; i < lim; i++) t[i] = 0;
	NTT(t, lim, 1), NTT(g, lim, 1);
	for (int i = 0; i < lim; i++) 
		g[i] = (2 - g[i] * t[i] % P + P) % P * g[i] % P;
	NTT(g, lim, -1);
	for (int i = n; i < lim; i++) g[i] = 0;
}

int C(int n, int m) {
	if (n < m || m < 0) return 0;
	return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

signed main() {
    n = rd(), w = rd(), init(n);
    f[0] = 1;
    for (int i = 2; i <= n; i++) 
    	f[i] = (P - 1) * ifac[i] % P * (i - 1) % P * qpow(w, i - 2) % P;
    INV(f, h, n + 1);
    for (int i = 0; i <= n; i++) 
    	(h[i] *= fac[i]) %= P;
    int res = 0;
    for (int i = 0; i <= n; i++) 
    	(res += C(n, i) * qpow(w, i) % P * h[n - i] % P) %= P;
    wr(res);
    return 0;
}