NOIP2019模拟2019.9.20】膜拜大会（外向树容斥，分类讨论）

传送门。

题解：

我果然是不擅长分类讨论，心态被搞崩了。

注意到\(m<=n-2\)，意味着除了1以外的位置不可能被加到a[1]两遍。

先考虑个大概：

考虑若存在\(x,x-1,…,2\)（有序）这样的，且1要么不出现，要么出现在2的左边，那么\(a[1]=\sum_{i=1}^x a[i]\)。

同样，若存在\(y,y+1,…,n\)，且1要么不出现，要么出现在n的左边，那么\(a[1]=a[1]+\sum_{i=y}^n a[i]\)。

开始讨论：

1.1没有出现，直接枚举x，求出最大的y的满足\(sum>=K\)，现在大概要求x要恰好，y要至少。

至少好算，恰好的话考虑用至少x减去至少x+1。

2.1出现了，1的右边只有2,，n要么不出现，要么出现在1的左边，注意这种情况下\(y->n\)的和依然会被加进a[1]，同样枚举x，求出最大的y，然后我们可以列出一个限制树，若\(j\)必须在\(i\)的左边，\(link(i,j)\)，根据CTS2019氪金手游那题，概率是\(\prod{1 \over siz}\)，乘上总方案数便是可行的方案数。

3.把上种情况的2、n互换，求法类似。

4.1出现了，2和n都在1的右边，注意这种情况\(a[1]\)会被加两遍，同样枚举x，求最大的y，然后列出限制树，发现并不是外向树，有一条内向边，那么直接把这条边容斥即可。

Code：

#include<bits/stdc++.h>

#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)

#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)

#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)

#define ll long long

#define pp printf

#define hh pp("\n")

using namespace std;

const int mo = 998244353;

ll ksm(ll x, ll y) {

	ll s = 1;

	for(; y; y /= 2, x = x * x % mo)

		if(y & 1) s = s * x % mo;

	return s;

}

const int N = 2e5 + 5;

int T, n, m, K;

ll a[N];

ll fac[N], nf[N], ni[N];

ll C(int n, int m) {

	return n < m || n < 0 || m < 0 ? 0 : fac[n] * nf[m] % mo * nf[n - m] % mo;

}

ll P(int n, int m) {

	return n < m || n < 0 || m < 0 ? 0 : fac[n] * nf[n - m] % mo;

}

ll p[N], q[N];

ll ans;

ll ca1(int x, int z) {

	return (x + z <= m) ? (C(m, x) * C(m - x, z) % mo * P(n - 1 - x - z, m - x - z) % mo) : 0;

}

void calc1() {

	int y = n + 1;

	fd(x, m + 1, 1) {

		while(y > 1 && p[x] + q[y] < K) y --;

		if(p[x] + q[y] < K) continue;

		int z = n - y + 1;

		ans += ca1(x - 1, z);

		ans -= ca1(x, z);

	}

	ans %= mo;

}

ll ca2(int x, int z) {

	if(x + z > m) return 0;

	return fac[m] * C(n - (x + z), m - (x + z)) % mo * nf[x - 2] % mo * nf[z + 1] % mo * ni[x + z] % mo;

}

void calc2() {

	int y = n + 1;

	fd(x, m, 2) {

		while(y > 1 && p[x] + q[y] < K) y --;

		if(p[x] + q[y] < K) continue;

		int z = n - y + 1;

		if(z > 0) {

			ans += ca2(x, z);

			ans -= ca2(x + 1, z);

		} else {

			n --;

			ans += ca2(x, z);

			ans -= ca2(x + 1, z);

			n ++;

			ans += ca2(x, 1);

			ans -= ca2(x + 1, 1);

		}

	}

}

void calc3() {

	int z = 1;

	fo(y, n - m + 1, n) {

		while(z < n && p[z] + q[y] < K) z ++;

		if(p[z] + q[y] < K) continue;

		int x = n - y + 2;

		if(z > 1) {

			ans += ca2(x, z - 1);

			ans -= ca2(x + 1, z - 1);

		} else {

			n --;

			ans += ca2(x, z - 1);

			ans -= ca2(x + 1, z - 1);

			n ++;

			ans += ca2(x, 1);

			ans -= ca2(x + 1, 1);

		}

	}

}

ll ca4(int x, int z) {

	if(x + z > m) return 0;

	ll sum = nf[z] * nf[x - 2] % mo * ni[x] % mo;

	sum = (sum - nf[z + 1] * nf[x - 2] % mo * ni[x + z] % mo + mo) % mo;

	return C(n - (x + z), m - (x + z)) * fac[m] % mo * sum % mo;

}

void calc4() {

	int y = n;

	fd(x, m, 2) {

		while(y > 1 && p[x] + q[y] + a[1] < K) y --;

		if(p[x] + q[y] + a[1] < K) continue;

		int z = n - y + 1;

		ans += ca4(x, z);

		ans -= ca4(x + 1, z);

	}

}

int main() {

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

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

	n = 2e5;

	fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;

	nf[n] = ksm(fac[n], mo - 2); fd(i, n, 1) nf[i - 1] = nf[i] * i % mo;

	fo(i, 1, n) ni[i] = ksm(i, mo - 2);

	for(scanf("%d", &T); T; T --) {

		scanf("%d %d %d", &n, &m, &K);

		fo(i, 1, n) scanf("%lld", &a[i]);

		if(K == 0) {

			pp("1\n"); continue;

		}

		q[n + 1] = p[0] = 0;

		fo(i, 1, n) p[i] = p[i - 1] + a[i];

		fd(i, n, 1) q[i] = q[i + 1] + a[i];

		ans = 0;

		calc1();

		calc2();

		calc3();

		calc4();

		ans = (ans % mo + mo) * ksm(P(n, m), mo - 2) % mo;

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

	}

}

巴特西

NOIP2019模拟2019.9.20】膜拜大会（外向树容斥，分类讨论）

题解：

Code：

最新文章

热门文章