您现在的位置是：首页 > 其他

当前栏目

NOI科目校信息学知识点测评-组合计数专题

知识点组合专题计数测评信息学

2023-09-27 14:28:26 时间

NOI科目校信息学知识点测评-组合计数专题

前言

这场比赛成功帮助我避免了低血压的风险呢！

A：格子染色

题目大意

给你值域数的个数，问你有多少个长度为 n 的数列满足连续的 l 个数中没有相同的。

思路

考虑你在中间的部分怎么放数。
那你前面的 $l$ 个互不相同，然后你下一个要和后面的 $l - 1$ 个互不相同，就没有别的要求，所以就是 $k - (l - 1)$ 个选项（ $k$ 是值域数的个数）
那后面选的概率就确定了，每个是 $k - l + 1$ 。
那我们再看一开始的，那如果 $n\leqslant$ 就全是前面的，至于这个前面的部分就是互不相同，那就直接组合数选要用的值，然后再一个阶乘选这些值排的顺序，就可以了。

代码

#include<cstdio>
#define ll long long
#define mo 1000000007

using namespace std;

const int N = 105;
int T, n, k, l;
ll jc[N], inv[N];

ll C(ll n, ll m) {
	if (m < 0 || m > n) return 0;
	return jc[n] * inv[m] % mo * inv[n - m] % mo;
}

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo; y >>= 1;
	}
	return re;
}

int main() {
	jc[0] = 1; for (int i = 1; i <= 100; i++) jc[i] = jc[i - 1] * i % mo;
	inv[0] = inv[1] = 1; for (int i = 2; i <= 100; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i = 1; i <= 100; i++) inv[i] = inv[i - 1] * inv[i] % mo;
	
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &n, &k, &l);
		if (n <= l) {
			printf("%lld\n", C(k, n) * jc[n] % mo);
			continue;
		}
		ll ans = C(k, l) * jc[l] % mo;
		ans = ans * ksm(k - l + 1, n - l) % mo;
		printf("%lld\n", ans);
	}
	
	return 0;
}

B：展览方案

题目大意

n 种物品每个有个数，然后要你选 m 个物品问你有多少选的方案。

思路

考虑到只有 $100$ 直接 DP。
设 $f_{i}$ 为当前选了 $i$ 个物品的方案，然后每次多一种物品你就枚举一开始的物品数和你这种物品放的个数转移。

代码

#include<cstdio>
#define mo 1000007

using namespace std;

const int N = 105;
int n, m, f[N], x, ff[N];

int main() {
	scanf("%d %d", &n, &m); f[0] = 1;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		for (int j = 0; j <= m; j++) ff[j] = 0;
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= x && k + j <= m; k++)
				(ff[j + k] += f[j]) %= mo;
		}
		for (int j = 0; j <= m; j++) f[j] = ff[j];
	}
	printf("%d", f[m]);
	
	return 0;
}

C：组数

题目大意

有 n 个节点，每个点度数不能超过一个值。
然后对于每个大小的树（就你可以选里面一些点形成这颗树），问你有多少棵树满足条件。

思路

你首先可以 DP，因为你会想到只要每个点的度数大于 $0$ 而且度数和等于 $2 n - 2$ （树 $n - 1$ 条边，每条边被两个端点各统计一次）。
但是你会发现每个点度数固定但是树的形态不是一定的。

那我们考虑怎么统计，考虑到无根树的统计不难想到一个东西叫做 prufer 序列，然后你会想到度数为 $x$ 的点在里面的出现次数是 $x - 1$ 次。
那我们就用重排的方案来求，每次你枚举点的度数 $x$ 就给 DP 里面的方案乘一个 $\dfrac{1}{(x-1)!}$ 。
然后最后给答案的时候给大小为 $x$ 的就乘上 $(x - 2)!$ 。
然后就可以正常 DP 了。

代码

#include<cstdio>
#include<iostream>
#define ll long long
#define mo 1004535809

using namespace std;

const int N = 205;
int n, m, x;
ll f[N][N], jc[N], inv[N];

int main() {
	jc[0] = 1; for (int i = 1; i <= 100; i++) jc[i] = jc[i - 1] * i % mo;
	inv[0] = inv[1] = 1; for (int i = 2; i <= 100; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i = 1; i <= 100; i++) inv[i] = inv[i - 1] * inv[i] % mo;
	
	scanf("%d", &n); f[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		for (int j = i - 1; j >= 0; j--)
			for (int k = 0; k < 2 * n - 2; k++) {
				for (int l = 1; l <= x && k + l <= 2 * n - 2; l++)
					(f[j + 1][k + l] += f[j][k] * inv[l - 1] % mo) %= mo;
			}
	}
	
	printf("%d ", n);
	for (int i = 2; i <= n; i++) printf("%lld ", f[i][(i - 1) * 2] * jc[i - 2] % mo);
	
	return 0;
}

D：美妙排列

题目大意

给你 n 个区间，每个对应你构造的排列中的第 i 个数，表示这个数是这个区间中最小的数。
然后问你能构造多少个排列满足这个条件。

思路

首先看到这个区间最小直接想到笛卡尔树。
然后你就考虑假设你现在在一个区间，然后又对应的点集。
那最小值放在哪里固定了，那剩下就你要把点集分成两个部分（大小固定）
那我们就可以直接乘一个组合数枚举点集给的位置。

然后你会发现这样搞会超时，因为你要找最小值的点，每次都是区间大小的复杂度，最坏的时候是平方的。
那我们考虑如果它真的是笛卡尔树的样子，那我们最终每个点都会作为一个区间，都要贡献，所以你可以直接枚举每个点直接贡献。
那问题就是判断是否是笛卡尔树了（因为如果笛卡尔树不可能构造的出来）。

那怎么判断呢？
我们考虑把区间从大到小排序，然后依次来看。
我们可以把当前没有被分割的区间做一个标记（我标记在了左端点，标记出右端点的位置）
然后对于一个区间，如果它左端点对应的区间和它这个区间不对应的话那就不行。
否则它就把这个区间分成了两个区间，以它的位置为断点。

然后这么判断一些就可以啦，复杂度是排序的 $n\log n$ 。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define mo 1000000007

using namespace std;

const int N = 1e6 + 100;
int n, ls[N], rs[N], cnt;
int L[N], R[N], dy[N];
ll jc[N], inv[N], ans;
struct node {
	int id, len;
}a[N];

int re; char c;
int read() {
	re = 0; c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0'; c = getchar();
	}
	return re;
}

ll C(int n, int m) {
	if (m < 0 || m > n) return 0;
	return jc[n] * inv[m] % mo * inv[n - m] % mo;
}

bool cmp(node x, node y) {
	return x.len > y.len;
}

void build(int l, int r) {
	if (l > r) return ;
	for (int i = l; i <= r; i++)
		if (L[i] == l && R[i] == r) {
			ans = ans * C(r - l, r - i) % mo;
			build(l, i - 1); build(i + 1, r); return ;
		}
//	ans = 0;
}

void work() {
	for (int i = 1; i <= n; i++) a[i] = (node){i, R[i] - L[i] + 1};
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++) dy[i] = 0; dy[1] = n;
	for (int i = 1; i <= n; i++)
		if (!dy[L[a[i].id]]) {ans = 0; return ;}
			else if (dy[L[a[i].id]] != R[a[i].id]) {ans = 0; return ;}
				else {
					dy[L[a[i].id]] = a[i].id - 1; dy[a[i].id + 1] = R[a[i].id];
				}
//	build(1, n);
	for (int i = 1; i <= n; i++) {
		ans = ans * C(R[i] - L[i], R[i] - i) % mo;
	}
}

int main() {
	jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = jc[i - 1] * i % mo;
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i = 1; i < N; i++) inv[i] = inv[i - 1] * inv[i] % mo;
	
	while (scanf("%d", &n) != EOF) {
		for (int i = 1; i <= n; i++) L[i] = read();
		for (int i = 1; i <= n; i++) R[i] = read();
		printf("Case #%d: ", ++cnt);
		ans = 1; work(); printf("%lld\n", ans);
	}
	
	return 0;
}

E：n维病毒

题目大意

问你 n 维上有多少个整点距离原点的距离不超过一个值 l。

思路

这题属实把我自己整不会了。
一开始看到这个这个首先转化成有多少个长度为 n 的序列它们每个数绝对值的和小于等于 l。
然后就开始刚生成函数，把人刚傻了。

结果找别人一看：这不是直接插板就好了吗？！
就直接插板得到每个位置放的个数，然后因为有正负我们可以枚举放的个数是 $0$ 的个数，然后插板变成每个只要要有数。

然后你想一下得到插板是 $\binom{l}{n-i}$ 然后一个 Lucas 得到 $\binom{l\bmod mo}{n-i}$ 。
（然后后面我们设 $l$ 自动取模）
然后你考虑怎么求这个组合数（因为上面还是很大）
考虑用阶乘那个求，那复杂度就是下面的，但是每个求还是不行。
然后你考虑怎么搞，就考虑两个之间变化了多少。

先看看 $i$ 到 $i + 1$ ：
$\binom{l}{n-i}=\dfrac{l!}{(n-i)!(l-n+i)!}$
$\binom{l}{n-i-1}=\dfrac{l!(n-i)}{(n-i)!(l-n+i)!(l-n+i+1)}$
那下面这个部分要逆元还是会 T。

考虑反过来，从 $i$ 到 $i - 1$ ：
$\binom{l}{n-i}=\dfrac{l!}{(n-i)!(l-n+i)!}$
$\binom{l}{n-i+1}=\dfrac{l!(l-n+i)}{(n-i)!(n-i+1)(l-n+i)!}$
然后你发现下面这个部分你可以预处理逆元了！

然后就可以做了。
（还有一个二的次方的变化过于简单不说了）

代码

#include<cstdio>
#include<iostream>
#define ll long long
#define mo 1000000007

using namespace std;

const ll N = 1e6 + 100;
ll T;
ll ans, jc[N], inv[N], n, l, invo[N];

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo; x = x * x % mo; y >>= 1;
	}
	return re;
}

ll C(ll n, ll m) {
	if (m < 0 || m > n) return 0;
	return jc[n] * inv[m] % mo * inv[n - m] % mo;
}

ll spC(ll n, ll m) {
	if (n < m) return 0;
	ll re = 1; for (ll i = n - m + 1; i <= n; i++) re = re * i % mo;
	re = re * inv[m] % mo; return re;
}

ll work(ll n, ll l) {
	if (!n) return 1;
	return spC(l % mo, n);
}

int main() {
	jc[0] = 1; for (ll i = 1; i <= 1000000; i++) jc[i] = jc[i - 1] * i % mo;
	inv[0] = inv[1] = 1; for (ll i = 2; i <= 1000000; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (ll i = 1; i <= 1000000; i++) invo[i] = inv[i], inv[i] = inv[i - 1] * inv[i] % mo;
	
	scanf("%lld", &T);
	while (T--) {
		scanf("%lld %lld", &n, &l); ans = 0;
		ll di = 1;
		ll wks = 0;
		for (ll i = n; i >= 0; i--) {
			if (!wks) wks = work(n - i, l);
			(ans += wks * di % mo * C(n, i) % mo) %= mo;
			di = di * 2 % mo;
			if (wks) wks = wks * (l % mo - n + i) % mo * invo[n - i + 1] % mo;
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}

猜你喜欢

在四川大学的第三个冠军在线编程竞赛：簿传输
Windows 10如何在命令行中执行Windows Defender
bootloader与启动地址偏移
PHP与Java进行通信的实现方法
精通Dubbo——Dubbo支持的协议的详解
SpringSecurity快速入门
python文件封装成*.exe文件（单文件和多文件）
Linux系统字符集乱码问题
安卓UI开发新技能-Jetpack Compose
mysql安装方式汇总
java项目部署
iOS开发基础知识--碎片34
揭秘最高5Gbps的以太网标准IEEE 802.3bz
二分法查找和分段线性插值算法在RTD中应用（转）

相关主题

python知识点
Sql知识点总结
linux知识点
网络知识点
React知识点
js知识点
JS 知识点
C++知识点
小知识点
一些知识点
Vue知识点（1）
高级知识点
新知识点
几个知识点
vue知识点总结

zl程序教程

当前栏目

NOI科目校信息学知识点测评-组合计数专题

NOI科目校信息学知识点测评-组合计数专题

前言

A：格子染色

题目大意

思路

代码

B：展览方案

题目大意

思路

代码

C：组数

题目大意

思路

代码

D：美妙排列

题目大意

思路

代码

E：n维病毒

题目大意

思路

代码

相关文章

当前栏目

NOI科目校 信息学知识点测评-组合计数专题

NOI科目校 信息学知识点测评-组合计数专题

前言

A：格子染色

题目大意

思路

代码

B：展览方案

题目大意

思路

代码

C：组数

题目大意

思路

代码

D：美妙排列

题目大意

思路

代码

E：n维病毒

题目大意

思路

代码

相关文章

NOI科目校信息学知识点测评-组合计数专题

NOI科目校信息学知识点测评-组合计数专题