【LOJ】#2541. 「PKUWC2018」猎人杀

题解

一道神仙的题><

我们毙掉一个人后总的w的和会减少，怎么看怎么像指数算法

然而，我们可以容斥……

设\(\sum_{i = 1}^{n} w_{i} = Sum\)

我们把问题转化一下，就是一个猎人死掉之后，并不认为他死掉了，他还活着，只是毙掉他的时候，再毙一次

很容易发现这是个正无穷的递归……但是……这是对的！

例如下一个毙掉\(i\)的概率，死掉的人的w和是\(B\),则

\(P = \frac{B}{A}P + \frac{w_{i}}{A}\)

我们当成一元一次方程解，很容易发现

\(P = \frac{w_{i}}{A - B}\)

很容易发现这个式子是对的

然后我们选出来一堆人，设这些人w的和为\(S\)

我们要求的是这些人在1号人以后毙掉的概率，剩下人随意

\(P = \sum_{i = 0}^{+\infty}(1 - \frac{S + w_{1}}{A})^{i} \frac{w_{1}}{A}\)

就是我们从除了第一个人和S这些人里找人毙掉，反正我们可以反复毙掉一个人，最后再乘上第一个人被毙掉的概率

这个式子可以写成这样

\(P = (1 - \frac{S + w_{1}}{A})P + \frac{w_{1}}{A}\)

解出来

\(P = \frac{w_{1}}{S + w_{1}}\)

……

好吧

然后我们显然容斥系数是(-1)的人数次幂，对于加入一个人，对系数的贡献是-1

我们可以用S进行分类，可以背包求出每个S的系数

然后发现这可以用生成函数进行优化\(\prod_{i = 2}^{n} (1 - x^{w_{i}})\)

很明显的分治NTT

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#define enter putchar('\n')

#define space putchar(' ')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define pii pair<int,int>

#define eps 1e-7

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

typedef vector<int> poly;

template<class T>

void read(T &res) {

	res = 0;char c = getchar();T f = 1;

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {putchar('-');x = -x;}

	if(x >= 10) {

		out(x / 10);

	}

	putchar('0' + x % 10);

}

const int MOD = 998244353,MAXL = 1 << 18;

int W[MAXL + 5],N,val[MAXN],sum;

poly ans;

int mul(int a,int b) {

	return 1LL * a * b % MOD;

}

int inc(int a,int b) {

	return a + b >= MOD ? a + b - MOD : a + b;

}

int fpow(int x,int c) {

	int res = 1,t = x;

	while(c) {

		if(c & 1) res = mul(res,t);

		t = mul(t,t);

		c >>= 1;

	}

	return res;

}

void NTT(poly &f,int L,int on) {

	f.resize(L);

	for(int i = 1 ,j = L / 2 ; i < L - 1 ; ++i) {

		if(i < j) swap(f[i],f[j]);

		int k = L / 2;

		while(j >= k) {

			j -= k;

			k >>= 1;

		}

		j += k;

	}

	for(int h = 2 ; h <= L ; h <<= 1) {

		int wn = W[(MAXL + on * MAXL / h) % MAXL];

		for(int k = 0 ; k < L ; k += h) {

			int w = 1;

			for(int j = k ; j < k + h / 2 ; ++j) {

				int u = f[j],t = mul(f[j + h / 2],w);

				f[j] = inc(u,t);

				f[j + h / 2] = inc(u,MOD - t);

				w = mul(w,wn);

			}

		}

	}

	if(on == -1) {

		int InvL = fpow(L,MOD - 2);

		for(int i = 0 ; i < L ; ++i) f[i] = mul(f[i],InvL);

	}

}

poly operator * (poly a,poly b) {

	int t = a.size() + b.size();

	int l = 1;

	while(l <= t) l <<= 1;

	NTT(a,l,1);NTT(b,l,1);

	poly c;c.clear();c.resize(l);

	for(int i = 0 ; i < l ; ++i) {

		c[i] = mul(a[i],b[i]);

	}

	NTT(c,l,-1);

	for(int i = l - 1 ; i >= 0 ; --i) {

		if(c[i] == 0) c.pop_back();

		else break;

	}

	return c;

}

void Init() {

	srand(20020421);

	W[0] = 1;W[1] = fpow(3,(MOD - 1) / MAXL);

	for(int i = 2 ; i < MAXL ; ++i) W[i] = mul(W[i - 1],W[1]);

	read(N);

	for(int i = 1 ; i <= N ; ++i) {read(val[i]);sum += val[i];}

	random_shuffle(val + 2,val + N + 1);

}

poly Solve(int l,int r) {

	if(l == r) {

		poly g;

		g.clear();

		g.resize(val[l] + 1);

		g[val[l]] = MOD - 1;g[0] = 1;

		return g;

	}

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

	return Solve(l,mid) * Solve(mid + 1,r);

}

int main() {

#ifdef ivorysi

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

#endif

	Init();

	if(N == 1) {

		puts("1");

		return 0;

	}

	ans = Solve(2,N);

	int res = 0;

	ans.resize(sum);

	for(int i = 0 ; i <= sum ; ++i) {

		res = inc(res,mul(ans[i],mul(val[1],fpow(val[1] + i,MOD - 2))));

	}

	out(res);enter;

	return 0;

}

巴特西

【LOJ】#2541. 「PKUWC2018」猎人杀

题解

代码

最新文章

热门文章