ACM中的整数K拆分 (有条件限制 无条件限制 插板法 URAL-1036 HDU-6397)

整数的K拆分

整数K拆分示例

在程序设计竞赛中,我们会经常遇到一类整数 $K$ 拆分的问题。

例如:求 $N$ 个非负整数之和为 $S$ 的方案数(每个数字都小于 $M$)。

对于这类问题,分为两种情况:①没有条件限制。 ②有条件限制。

没有条件限制

当 $N = 2,S = 4$ 时,有

$1.\quad0 + 4$
$2.\quad1 + 3$
$3.\quad2 + 2$
$4.\quad3 + 1$
$5.\quad4 + 0$

对于没有条件限制的问题,直接使用插板法求解即可。
例如要用 $n$ 个数字之和等于 $s$。不妨假设要把 $s$ 个球,用 $n -1$ 块板分为 $n$ 组(可为空集)。这样子,用板隔开的球数,就是划分出的 $n$ 个数。
例如 $n = 4,s = 10$ 时,我们可以找到一种情况为 $1 + 5 + 0 + 4$,即:

因此我们可以看成在 $n - 1 + s$ 个空位上,选择 $n - 1$ 个位置来插入板,将数字隔开。即:

有条件限制

有条件限制的类型题目通常为:

例如:求 $n$ 个非负整数之和为 $s$ 的方案数,每个数字都小于 $m$。

例如 $n = 2,s = 6,m = 5$:

$1.\quad2+4$
$2.\quad3+3$
$3.\quad4+2$

对于这种情况,我们也可以使用插板法 + 容斥原理。
首先要知道,我们使用容斥原理的步骤是:先把没有限制的情况算出来 $-$ 不符合条件的情况。
上面已经讲到,没有限制条件的情况总数为 $C_{n-1+s}^{n-1}$。

而我们接下来只需要算不符合条件的情况,即存在至少一个数字不小于给定的 $m$。
显然,计算不符合条件的情况总数是 至少一个位置不符合条件的总数 减去 至少两个位置不符合条件的总数 加上 至少三个位置符合条件的种数……

那怎么计算至少 $i$ 个位置不符合条件的总数呢?
假设题目为: 求 $n$ 个非负整数之和为 $s$ 的方案数,每个数字都小于 $m$。

我们想计算出不符合条件的情况,我们可以考虑构造出不符合条件的情况。
如果我们取出 $im$ 个小球出来,再对 $n-1+s-im$ 个小球使用一样的插板法。即得 $C_{n-1+s-im}^{n-1}$。
然后我们再将这取出来的 $i*m$ 个小球分成 $i$ 组,每组 $m$ 个。在上述插完板后的 $n$ 个空隙中,选择 $i$ 个不同的位置,把 $i$ 组小球塞回到插板中。

如此一来,就可以构造出 $i$ 个数字不符合条件的情况。即:

但是还需要容斥,即:

Lucky Tickets URAL - 1036

题意

给定一个 $N$ 和一个 $S$ ,存在某些数字长度为 $2N$ 且前后两部分的和相等,而且要求整个数字的和为 $S$ ,问你这样数字的个数。

题解

可以发现,我们只需要找到 $N$ 个数字和为 $\frac{S}{2}$ 的数字个数,然后平方一下就是答案所求的方案数。
不难发现还有一个要求是每一位数字都是 $0$ 到 $9$ 的。

于是我们可以得到这么一个式子:

由于数字较大,所以使用了 JAVA 的大数

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
import java.util.*;
import java.math.*;

public class Main {

static BigInteger C(int n, int m) {
if (m > n) return BigInteger.ZERO;
BigInteger ans = BigInteger.ONE;
for (int i = 0; i < m; i++) {
ans = ans.multiply(BigInteger.valueOf(n - i));
ans = ans.divide(BigInteger.valueOf(i + 1));
}
return ans;
}

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt(), s = cin.nextInt();
if (s%2 == 1) {
System.out.println("0");
return;
}
BigInteger ans = BigInteger.ZERO;
for (int i = 0; i <= n; i++) {
BigInteger delta = C(n - 1 + s/2 - i*10, n - 1).multiply(C(n, i));
ans = ans.add(BigInteger.valueOf((long)Math.pow(-1, i%2)).multiply(delta));
}
System.out.println(ans.multiply(ans));
}

}

Character Encoding HDU - 6397

题意

求把 $k$ 分解为 $m$ 部分,且每部分都小于 $n$ 的方案数( $mod\ 998244353$ )。

题解

这道题也是普通的整数 $k$ 拆分。只不过加上了 $mod\ 998244353$ 而已。
由于答案要膜一个数,所以就把组合数用逆元求就行了。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int maxn = 3e5 + 10;
LL fact[maxn], inv[maxn], T, n, m, k, ans;

LL power(LL a, int x) {
LL ans = 1;
while (x) {
if (x & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
x >>= 1;
}
return ans;
}

void init() {
fact[0] = 1;
for (int i = 1; i < maxn; i++) {
fact[i] = fact[i - 1] * i % mod;
}
inv[maxn - 1] = power(fact[maxn - 1], mod - 2);
for (int i = maxn - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % mod;
}
}

LL C(LL n, LL m) {
if (m > n) return 0;
return (fact[n] * inv[n - m]) %mod * inv[m] % mod;
}


int main()
{
init();
scanf("%lld", &T);
while (T--) {
scanf("%lld %lld %lld", &n, &m, &k);
ans = C(k + m - 1, m - 1);
for (int i = 1; i <= m; i++) {
ans = (ans + (LL)pow(-1, i%2) * (C(k + m - 1 - n * i, m - 1) * C(m, i))%mod + mod)%mod;
}
printf("%lld\n", ans %mod);
}

return 0;
}

后记

其实还有一道题是每一个位置都有不同条件限制,暂时没有找到那道题。