一开始有nn个猎人，第ii个猎人有仇恨度wiw_i，每个猎人死亡后必须开一枪，且被射中的人也会死亡。

假设当前还活着的猎人有[i1...im][i_1...i_m]，那么有wik∑j=1mwij\frac{w_{i_k}}{\sum\limits_{j=1}^{m}w_{i_j}}概率是向猎人iki_k开枪。

一开始第一枪由你打响，目标的选择方法和猎人一样，求11号猎人最后一个死的的概率。

答案对998244353998244353取模

wi>0,1≤∑wi≤100000w_i>0, 1\le\sum w_i\le 100000

LOJ2541

Solution

考虑开枪时，如果打到死掉的猎人，就再打一枪，一直到打到活着的猎人停止

不难发现，这和原问题的概率是一样的

感性理解，每次如果没打中，再新打一枪的时候对于活着的人被打中的概率还是和上一轮一样的

题目要求11号猎人后面恰好没有人死的概率，考虑容斥，枚举在他后面死的人

设SS为枚举到的人的wiw_i的和，AA表示∑i=1nwi\sum\limits_{i=1}^{n}w_i那么有

ans=(−1)∣S∣∑i=0∞(1−S+w1A)iw1A ans = (-1)^{|S|} \sum_{i=0}^{\infty} (1-\frac{S+w_1}{A})^i\frac{w_1}{A}

后面那一坨无限概率怎么算呢？

令

T=∑i=0∞(1−S+w1A)i T = \sum_{i=0}^{\infty} (1-\frac{S+w_1}{A})^i

那么有

(1−S+w1A)T=∑i=1∞(1−S+w1A)i (1-\frac{S+w_1}{A})T=\sum_{i=1}^{\infty} (1-\frac{S+w_1}{A})^i

作差可以得到

T=AS+w1 T=\frac{A}{S+w_1}

所以答案就是ans=(−1)∣S∣w1S+w1ans=(-1)^{|S|}\frac{w_1}{S+w_1}

注意到题目∑wi\sum w_i比较小，所以可以考虑对于每个SS，求出它前面的容斥系数的和

这个可以直接构造生成函数∏i=2n(1−xwi)\prod\limits_{i=2}^{n}(1-x^{w_i})，用分治+NTT在O(nlog2n)O(n\log^2n)的时间复杂度内快速计算

Summary

这道题前面推概率那里实在是太神仙了

倒是后半部分用NTT优化比较套路，比较容易想

这道题思维难度还是挺大的。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

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

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 1e5 + 100, Mod = 998244353, g = 3;

int N, W[Maxn];

vector <int> F[Maxn << 2];
int cnt;

inline int Pow (int a, int b)
{
	int ans = 1;
	for (int i = b; i; i >>= 1, a = (LL)a * a % Mod) if (i & 1) ans = (LL)ans * a % Mod;
	return ans;
}

namespace Poly
{
	int n, rev[Maxn << 2], A[Maxn << 2], B[Maxn << 2];

	inline void DFT (int *A, int flag)
	{
		for (int i = 0; i < n; ++i) if (i < rev[i]) swap(A[i], A[rev[i]]);

		for (int mid = 1; mid < n; (mid <<= 1))
		{
/**/		int Wn = Pow(g, (Mod - 1) / mid / 2);
			if (flag < 0) Wn = Pow(Wn, Mod - 2);

			for (int i = 0; i < n; i += (mid << 1))
			{
				int W = 1;
				for (int j = i; j < i + mid; ++j, W = (LL)W * Wn % Mod)
				{
					int x = A[j], y = (LL)W * A[j + mid] % Mod;
					A[j] = (x + y) % Mod, A[j + mid] = (x - y + Mod) % Mod;
				}
			}
		}

		int inv = Pow(n, Mod - 2);
		if (flag < 0) for (int i = 0; i < n; ++i) A[i] = (LL)A[i] * inv % Mod;
	}

	inline vector <int> NTT (vector <int> F, vector <int> G)
	{
//		for (int i = 0; i < F.size(); ++i) cout<<F[i]<<" "; puts("");
//		for (int i = 0; i < G.size(); ++i) cout<<G[i]<<" "; puts("");
		int N = F.size(), M = G.size(); n = 1;
		for (int i = 0; i < N; ++i) A[i] = F[i];
		for (int i = 0; i < M; ++i) B[i] = G[i];

		while (n <= N + M) n <<= 1;
		for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) + (i & 1 ? (n >> 1) : 0);
		for (int i = N; i <= n; ++i) A[i] = 0;
		for (int i = M; i <= n; ++i) B[i] = 0;

		DFT (A, 1), DFT (B, 1);
		for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * B[i] % Mod;
		DFT (A, -1);

		for (int i = 0; i < N; ++i) F[i] = A[i];
		for (int i = N; i < N + M; ++i) F.pb(A[i]);
//		for (int i = 0; i < F.size(); ++i) cout<<F[i]<<" "; puts("");puts("");
		return F;
	}
}

inline int solve (int l, int r)
{
	int id = ++cnt;
	if (l == r)
	{
		F[id].pb(1); for (int i = 1; i < W[l]; ++i) F[id].pb(0); F[id].pb(Mod - 1);
		return id;
	}

	int mid = l + r >> 1;
	int lid = solve (l, mid), rid = solve (mid + 1, r);

	F[id] = Poly :: NTT (F[lid], F[rid]);
	
	return id;
}

inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

inline void Solve ()
{
	solve (2, N);

	int ans = 0;
//	for (int i = 0; i <= sum; ++i) cout<<F[1][i]<<" ";
//	puts("");
	for (int i = 0; i < F[1].size(); ++i)
		if (F[1][i]) 
			Add (ans, (LL)W[1] * Pow((i + W[1]) % Mod, Mod - 2) % Mod * F[1][i] % Mod);
	cout<<ans<<endl;
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i) W[i] = read<int>();
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}