#565. 「LibreOJ Round #10」mathematican 的二进制（期望 + 分治NTT）

时间：2023-03-08 17:26:50
#565. 「LibreOJ Round #10」mathematican 的二进制（期望 + 分治NTT）

题面

戳这里，题意简单易懂。

题解

首先我们发现，操作是可以不考虑顺序的，因为每次操作会加一个 \(1\) ，每次进位会减少一个 \(1\) ，我们就可以考虑最后 \(1\) 的个数（也就是最后的和），以及成功操作次数，就行了。

然后根据期望的线性性，我们可以从低到高按位考虑贡献。

考虑一个递推：\(f(i, j)\) 表示从后往前第 \(i\) 位总共被改变 \(j\) 次的概率，那么有两种转移：

  • 进位：\(\displaystyle f(i - 1, j) \to f(i, \lfloor \frac j 2 \rfloor)\)
  • 操作：对于第 \(i\) 位每个概率为 \(p\) 的操作， \(f(i, j - 1)p + f(i, j)(1 - p) \to f(i, j)\)

注意要先转移第一个，再转移第二个，因为第二个可以对于第一个操作上来的数位进行贡献。

然后这样直接实现就是 \(O(m^2)\) 的，但是我们可以考虑优化，对于第二个容易观察就是乘上了 \(P(x) = \prod_i p_ix + (1-p_i)\) 这个生成函数。

显然这个我们可以利用 **分治 \(NTT\) ** 来解决。

进位的话我们可以暴力进位，因为每个操作对于 **分治 \(NTT\) ** 的贡献可以放缩成一个等比级数：\(\displaystyle \sum_{i = 0} ^ {\infty} 2^{-i} = 2\) 。

所以最后时间复杂度就是 \(O(m \log^2 m)\) 的。

总结

对于一些期望题，可以考虑期望的线性性，以及试试操作顺序是否不影响答案。

然后考虑 \(NTT\) 优化概率生成函数就行啦。

代码

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << (x) << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

#define pb push_back

using namespace std;

typedef long long ll;

template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}

template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}

inline int read() {

	int x(0), sgn(1); char ch(getchar());

	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;

	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

	return x * sgn;

}

void File() {

#ifdef zjp_shadow

	freopen ("565.in", "r", stdin);

	freopen ("565.out", "w", stdout);

#endif

}

const int N = 200100, Mod = 998244353;

ll fpm(ll x, int power) {

	ll res = 1;

	for (; power; power >>= 1, (x *= x) %= Mod)

		if (power & 1) (res *= x) %= Mod;

	return res;

}

inline int Add(int a, int b) { return (a += b) >= Mod ? a - Mod : a; }

template<int Maxn>

struct Number_Theoretic_Transfrom {

	const int g = 3;

	ll powg[Maxn + 5], invpowg[Maxn + 5]; int rev[Maxn + 5];

	void NTT_Init() {

		for (int i = 2; i <= Maxn; i <<= 1)

			invpowg[i] = fpm((powg[i] = fpm(g, (Mod - 1) / i)), Mod - 2);

	}

	int len;

	void NTT(ll P[], int opt) {

		For (i, 0, len - 1)

			if (i < rev[i]) swap(P[i], P[rev[i]]);

		for (int i = 2, p = 1; i <= len; p = i, i <<= 1) {

			ll Wi = opt == 1 ? powg[i] : invpowg[i];

			for (int j = 0; j < len; j += i) {

				ll x = 1;

				For (k, 0, p - 1) {

					ll u = P[j + k], v = P[j + k + p] * x % Mod;

					P[j + k] = Add(u, v);

					P[j + k + p] = Add(u, Mod - v);

					(x *= Wi) %= Mod;

				}

			}

		}

		if (!~opt) {

			ll invn = fpm(len, Mod - 2);

			For (i, 0, len - 1) (P[i] *= invn) %= Mod;

		}

	}

	ll A[Maxn + 5], B[Maxn + 5];

	void Mult(int *a, int *b, int *c, int lena, int lenb) {

		int cnt = 0;

		for (len = 1; len <= lena + lenb; len <<= 1) ++ cnt;

		For (i, 0, len - 1)

			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1));

		For (i, 0, len - 1)

			A[i] = i <= lena ? a[i] : 0, B[i] = i <= lenb ? b[i] : 0;

		NTT(A, 1); NTT(B, 1); For (i, 0, len - 1) (A[i] *= B[i]) %= Mod; NTT(A, -1);

		For (i, 0, lena + lenb) c[i] = A[i];

	}

};

Number_Theoretic_Transfrom<1 << 20> NTT;

int n, m;

int pool[N << 5], *ptr = pool;

struct Poly {

	int *a, len;

	Poly(int l) { a = ptr; ptr += (len = l) + 1; }

	void Out() {

		debug(len);

		For (i, 1, n) printf ("%d%c", a[i], i == iend ? '\n' : ' ');

	}

};

inline bool operator < (const Poly &lhs, const Poly &rhs) {

	return lhs.len > rhs.len;

}

vector<int> Base[N];

Poly I(0);

Poly Calc(int id) {

	if (!(bool)Base[id].size()) return I;

	priority_queue<Poly> P;

	for (int prob : Base[id]) {

		Poly cur(1);

		cur.a[1] = prob;

		cur.a[0] = Mod + 1 - prob;

		P.push(cur);

	}

	while (P.size() > 1) {

		Poly a = P.top(); P.pop();

		Poly b = P.top(); P.pop();

		Poly c(a.len + b.len);

		NTT.Mult(a.a, b.a, c.a, a.len, b.len);

		P.push(c);

	}

	return P.top();

}

int main () {

	File();

	NTT.NTT_Init();

	n = read(); m = read();

	For (i, 1, m) {

		int pos = read(), x = read(), y = read();

		Base[pos].pb(1ll * x * fpm(y, Mod - 2) % Mod);

	}

	ll ans = 0;

	Poly res(0); res.a[0] = 1;

	For (i, 0, n + 20) {

		Poly tmp = Calc(i);

		if (tmp.len) {

			NTT.Mult(res.a, tmp.a, res.a, res.len, tmp.len);

			res.len = res.len + tmp.len;

		}

		For (j, 0, res.len) {

			ans = (ans + 1ll * res.a[j] * j) % Mod;

			int temp = res.a[j]; res.a[j] = 0;

			(res.a[j >> 1] += temp) %= Mod;

		}

		res.len >>= 1;

	}

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

	return 0;

}