「Solution」组合数学测试

Posted on Edited on In

组合数学测试题解

T1

jump

link

分析

感性观察+手玩可以在5min内得到结论。
走的路径如下图所示。
T1
如果行比列多，就把行列反过来。
得到式子是:$\dbinom{n + m + 1}{m + 1} + m$，上下项的差很小，可以暴力求。

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 2000005;
const int Mod = 1e9 + 7;

int n, m, ans;

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = res * x % Mod;
		x = x * x % Mod;
		y >>= 1;
	}
	return res;
}

int C(int x, int y) {

	if ((x - y) > (x - (x - y))) y = x - y;

	int res = 1ll;
	for (int i = y + 1; i <= x; i++) {
		res = (res * (i % Mod)) % Mod;
	}

	for (int i = 1; i <= x - y; i++) {
		res = (res * qpow(i, Mod - 2) % Mod);
	}

	return res;

}

signed main() {

	freopen("jump.in", "r", stdin);
	freopen("jump.out", "w", stdout);

	scanf("%lld %lld", &n, &m);
    if (n > m) swap(n, m);

    ans = (C(n + m + 1, m + 1) + m) % Mod;
    printf("%lld\n", ans);

	return 0;
}

T2

count

link

分析

其实就是个康托展开。

考试时真心没搞清楚题意，于是放弃了。。。
但是有重复元素。 可以用如下流程操作。

  • 用桶记录每个数的个数。
  • 对于每一位，枚举小于当前位的数字
  • 如果还有可用的，填进去，计算后面的数字产生全排列的贡献
  • 把当前位的数字个数减一

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 55;

char s[MAXN];
int n, ans, tot[MAXN], C[MAXN][MAXN];

signed main() {

    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);

    C[0][0] = 1;
    for (int i = 1; i <= 50; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }

    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        tot[s[i] - 48]++;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < s[i] - 48; j++) if(tot[j] > 0) {
            tot[j]--;
            int res = 1, sum = n - i;
            for(int k = 0; k <= 9; k++) {
                res *= C[sum][sum - tot[k]];
                sum -= tot[k];
            }
            tot[j]++;
            ans += res;
        }
        tot[s[i] - 48]--;
    }

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

    return 0;
}

T3

encoding

link
我是真的脑子进水了。
居然忘了乘每项前的系数，看了半天还没发现。

分析

直接隔板法。
方案中如果不考虑数字的limit，那么可以有$\dbinom{m + k - 1}{m - 1}$。
然后枚举有多少个填进去的数不合法。

方案数是 $\dbinom{k + m - 1 - i \times n}{m - 1}$，注意不合法的板子可以插的地方不唯一，要乘上系数 $\dbinom{m}{i}$。
结果写着写着就忘了。

本题就可以直接奇减偶加容斥求解。

$Ans = \dbinom{k + m - 1}{m - 1} - {\Large\sum_{i = 1}^n} \dbinom{k + m - 1 - i \times n}{m - 1} \dbinom{m}{i} \times (-1)^i$

代码

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
#define LL long long
using namespace std;
const int MAXN = 1e5 + 5;
const int Mod = 998244353;

int t, n, m, k;

LL fac[MAXN << 1], inv[MAXN << 1], ans;

LL qpow(LL x, int y) {
	LL res = 1;
	while (y) {
		if (y & 1) res = res * x % Mod;
		x = x * x % Mod;
		y >>= 1;
	}
	return res;
}

LL C(int x, int y) {
    if (y > x) return 0;
    if (x < 0 || y < 0) return 0;
	return fac[x] * inv[y] % Mod * inv[x - y] % Mod;
}

signed main() {

    freopen("encoding.in", "r", stdin);
    freopen("encoding.out", "w", stdout);

    fac[0] = inv[0] = 1;
	for (int i = 1; i <= 2e5; i++) fac[i] = fac[i - 1] * i % Mod;
	inv[200000] = qpow(fac[200000], Mod - 2);
	for (int i = 2e5 - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % Mod;

    scanf("%lld", &t);

    while (t--) {
        scanf("%lld %lld %lld", &n, &m, &k);
        LL ans = C(k + m - 1, m - 1);
        for (int i = 1, sta = -1; i <= m; i++, sta *= -1) {
            ans = (ans + C(k + m - 1 - i * n, m - 1) * C(m, i) * (sta) + Mod) % Mod;
        }
        printf("%lld\n", ans);
    }

    return 0;
}

T4

against

link

数组开小了 + cmp函数自带大场数 + 忘记处理循环后的遗留数据 = 0

分析

没什么好说的。。。

在代码里把错误标出来吧。。。

代码

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
#include <ctime>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 2e6 + 5;

int n, tot[MAXN], cnt, ans, sum;

struct node {
	int v[6], wid;
	unsigned long long key;
} s[MAXN], tmp[MAXN];

bool check(int x, int y) {
	bool flag = true;
	for (int i = 1; i <= 5; i++) if(tmp[x].v[i] != tmp[y].v[i]) {
		flag = false;
		break;
	}
	return flag;
}

bool cmp(node x, node y) {
	if (x.wid != y.wid) return x.wid < y.wid;
    // 哈哈，sort直接TLE
	// for (int i = 1; i <= 5; i++) {
	// 	if (x.v[i] != y.v[i]) {
	// 		return x.v[i] < y.v[i];
	// 	}
	// }
	// return true;
	return x.key < y.key;
}

void read(int& x) {
	x = 0;
	int f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f = -f;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	x *= f;
}

signed main() {

	freopen("against.in", "r", stdin);
	freopen("against.out", "w", stdout);

	read(n);

	// double st1 = time(0);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 5; j++) {
			read(s[i].v[j]);
		}
		sort(s[i].v + 1, s[i].v + 1 + 5);
		for (int sta = 1; sta < (1 << 5); sta++) {
			cnt++; int p = 0;
			for (int k = 1; k <= 5; k++) if ((1 << k - 1) & sta) {
				tmp[cnt].v[++p] = s[i].v[k];
				tmp[cnt].key = tmp[cnt].key * 13331 + s[i].v[k]; // 考试没有hash，直接cmp自带大常数
			}
			tmp[cnt].wid = p;
		}
	}

	// double st = time(0);

	// printf("%ld\n", st - st1);

	sort(tmp + 1, tmp + 1 + cnt, cmp);

	// double ed = time(0);

	// printf("%lf\n", ed - st);  没有hash的排序跑了 9ms 哈哈哈哈。。。

	// for (int i = 1; i <= cnt; i++) {
	//     printf("%d : ", i);
	//     for (int j = 1; j <= 5; j++) {
	//         printf("%d ", tmp[i].v[j]);
	//     }
	//     printf("\n");
	// }

	ans = 0, sum = 0;

	for (int i = 1; i <= cnt; i++) {
		if (check(i, i - 1)) {
			sum++;
		} else {
			tot[tmp[i - 1].wid] += (sum * (sum - 1)) / 2;
			sum = 1;
		}
	}
	tot[tmp[cnt - 1].wid] += (sum * (sum - 1)) / 2;  // 考试时没写，结果过样例了。哈哈哈哈。

	for (int i = 1, sta = 1; i <= 5; i++, sta *= -1) {
		// printf("%lld\n", tot[i]);
		ans += sta * tot[i];
	}

	// printf("%d\n", ans);
	printf("%lld\n", ((long long)n * (n - 1) / 2) - ans);

	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」