小红定义一个字符串的“连续段”数量为:相同字符的极长连续子串的数量。例如,"aabbaaa"共有 3 个连续段:"aa"+"bb"+"aaa"。 现在,小红希望你求出,长度为x+y,包含恰好有x个'a'和y个'b'组成的字符串,连续段数量恰好为i的字符串数量。你需要回答i∈[1,x+y]的每个i的答案。

输入格式

两个正整数x,y,用空格隔开。 1 ≤ x,y ≤ 1000

输出格式

输出共x+y行,第i行代表连续段数量为 i 的字符串数量。由于答案可能过大,请对 10**9 +7取模。

数据范围: 1 ≤ x,y ≤ 1000

输入样例:

2 1

输出样例:

0
2
1

在分析这道题之前,我们先引入 隔板法

从$10$个球中选择,要求放入$3$个盒子中。

这个问题等同于将$10$个球通过$2$个板子隔离成$3$个部分。

例如:

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、......

通常,将$10$个球放入$3$个盒子中的方法总数为${\binom {10-1}{3-1}}={\binom {9}{2}}=36$。

一般来说,将$n$个球放入$k$个盒子中的方法总数为${\binom {n-1}{k-1}}$。

这个问题可以等同于求解$x{1}+x{2}+...+x_{k}=n$的正整数解的数量。

我们再看这道题:

两种元素分别有 x, y 个,问 段数分别为 [1, x + y] 的摆放方式分别有多少种。

假设段数为 i ,因为只可能有 xy元素段交叉排序,所以:

  • 如果 i 为偶数,两种元素段数都为 i / 2
  • 如果 i 为奇数,那么开头元素有 i / 2 + 1 段,另一个有 i / 2 段。

我们通过 隔板法 可以很容易的得到答案: $$ f(i, x, y) = \begin{cases} \binom{x - 1}{\frac{i}{2} + 1 - 1} \cdot \binom{y - 1}{\frac{i}{2} - 1} + \binom{y - 1}{\frac{i}{2} + 1 - 1} \cdot \binom{x - 1}{\frac{i}{2} - 1} & \text{如果 } i \text{ 是奇数} \ 2 \cdot \binom{x - 1}{\frac{i}{2} - 1} \cdot \binom{y - 1}{\frac{i}{2} - 1} & \text{如果 } i \text{ 是偶数} \end{cases} $$

在本题中,为了减少计算量,我们可以打表组合数。

因为数据量比较小,我们可以通过 DP 来计算组合数: $$ C(i,j) = C(i - 1, j - 1) + C(i - 1, j) $$ 理解:对于 i 个里面选 j 个的组合数, 我们假定已经选择了一个, 那么有两种情况:

  • i - 1, j - 1
  • i - 1, j

代码实现

#include <iostream>
using namespace std;
using LL = long long;
const int N = 2e3 + 10, MOD = 1e9 + 7;

int x, y;
LL c[N][N];
LL C(LL a, LL b) {
    if(a < 0 || b < 0 || b > a) return 0;
    return c[a][b];
}
LL calc(LL i, LL x, LL y) {
    int l1 = i / 2 + (i & 1), l2 = i / 2;
    return (C(x - 1, l1 - 1) * C(y - 1, l2 - 1)
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 0; i < N; ++i)
        for(int j = 0; j <= i; ++j)
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j])
    cin >> x >> y;
    for(int i = 1; i <= x + y; ++i)
        cout << calc(i, x, y) << '\n';
    return 0;
}
分类: Math

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status