考虑模拟整个划分过程。
划分过程:
1. 在 $m$ 个数中选择 $2 \times n$ 个数。(一个数可以被选多次)
2. 将 $2 \times n$ 个数划分。
根据题目可得第2步方案一定唯一,所以考虑第1步方案即可。
我们设 $x_i$ 代表数 $i$ 被选了多少次,则:
$$\sum\limits _ {i = 1} ^ m x_i = 2 \times n \ (x[i] \in \mathbb{N})$$
而这个等式让我们想到了 「隔板法解决求和式不定方程」
的板子
我们定义 ${x’}_i = x_i + 1$,那么,原式就变为了:
$$\sum\limits _ {i = 1} ^ m {x’}_i = 2 \times n + m \ (x[i] \in \mathbb{N+})$$
此时我们就可以用 隔板法
解决了,公式为:($ans$ 代表答案)
$$ans = C _ {2 \times n + m - 1} ^ {m - 1}$$
由于只涉及到一个组合数,所以可以将数据范围扩大到「线性对数级别」(此处指可以在 $O(x \log y)$ 的时间复杂度内解决的问题,其中 $x$ 和 $y$ 是与读入数据有关的值;做法参见AcWing 886),即约 $10 ^ 5 \sim 10 ^ 6$ 级别
注解:
$\mathbb{N}$:代表所有自然数集合
$\mathbb{N+}$:代表所有正整数集合(即在 $\mathbb{N}$ 中去掉 $0$ 后的集合)
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, INF_BIT = 0x3f;
const int A = 1030, B = 1010, MOD = 1e9 + 7;
int m, n;
int c[A][B];
int main(){
scanf("%d%d", &m, &n);
int a = 2 * n + m - 1, b = m - 1;
for(int i = 0;i <= a;i++)
for(int j = 0;j <= min(i, b);j++)
if(j == 0) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
printf("%d\n", c[a][b]);
return 0;
}
后记
我比赛(实际上是模拟赛,即模拟AcWing“历年”周赛)时写了个
DP
,而这种写法比DP
的写法足足快了 $105\ \text{ms}$(原写法 $151\ \text{ms}$,新写法 $46\ \text{ms}$)