自动搬运

查看原文

来自洛谷，原作者为

	muqi132 **

搬运于2025-08-24 22:51:41，当前版本为作者最后更新于2024-10-24 13:08:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9768 A+B题解

我们首先注意到每一列是绑定在一起的，同时这一列能否成立只与前一列是否要求进位以及后一列是否进位有关。

所以我们观察到每一列有两个性质：自己能能否产生进位，自己是否需要进位，我们令 $need$ 为每一列需要的进位数，$make$ 用来描述这一列是否产生进位。

首先如果 $need$ 大于 $1$ 那么我们直接输出 $0$ 即可，因为在加法中进位数不可能超过 $1$。

我们根据 $need$ 和 $make$ 的值的不同将各列划分为四种点。

1. $need=make=1$，为 $A$ 类点。
2. $need=1,make=0$，为 $B$ 类点。
3. $need=0,make=1$，为 $C$ 类点。
4. $need=make=1$，为 $D$ 类点。

令 $A,B,C,D$ 四类点的数目分别为 $A,B,C,D$。

对于首位的，其不能产生进位，也就是 $A$ 类点，$B$ 类点才能作为开头。

对于末尾的，其不能需要进位，也就是 $A$ 类点，$C$ 类点才能作为结尾。

观察性质可以发现，所有合法序列都形如$\_B\_C\_C\_B\_C…B\_C\_$。

那么 $A$ 类点只存在于 $B$ 类点前的空格以及最后一个空格(有 $B+1$ 个位置可以选择)， $D$ 类点只存在于 $C$ 类点前的空格(有 $B$ 个位置可以选择)。

注意到只能以 $A$ 类点 $B$ 类点开头，以 $A$ 类点 $C$ 类点结尾，且 $A$ 类点无法放在 $B$ 类点之后，那么可以说明每个 $B$ 类点都与一个 $C$ 类点匹配，即 $B=C$。（根据 $need$ 和 $make$ 值的不同可以判断各点之间必须满足的位置关系）。

我们首先来考虑没有前导零的情况。

如果 $B=C=0，D>0$ 的话，$A$ 类点无论是前后都不能接 $D$ 类点，答案为 $0$，如果此时 $D=0$，那么答案为 $A!$，因为 $A$ 类点可以自由排列。

如果 $B=C>0$，则依次考虑每个数的情况。

1. $A$：其放在$B$前的任意位置或者最后一个位置，也就是一共 $B$ 个挡板，求 $A$ 个球有多少种放法，答案为$\frac{(A+B)!}{B!}$。
2. $B,C$：显然都是 $B!$ (注意 $B=C$)。
3. $D$：和 $A$ 同理,但是少一个位置,答案是$\frac{(D+B-1)!}{(B-1)!}$。

最后答案就是各自相乘为$(A+B)!\times(D+B-1)!\times{B}$。

前面都没有考虑前导零，那么现在我们需要考虑了。

因为开头是 $A$ 类点或者 $B$ 类点，所以我们只需要考虑 $A$ 类点和 $B$ 类点为0的情况，分别记数量为 $A_0,B_0$。

首先是特判，$B!=C$ 或者 $B=C=0，D>0$ 都返回 $0$，若 $B=C=D=0$，则答案容易知道为:$(A-1)!(A-A_0)$，解释如下：第一个位置有 $(A-A_0)$ 种放法，后面的位置就可以全排了。

然后考虑一般情况,即 $B=C>0$。

我们考虑对于以 $A$ 类点为起点和以 $B$ 类点为起点各自单独计算 $ans_A$ 和 $ans_B$。

1. $ans_A$：对于 $A$ 类点,此时第一位为情况为 $A-A_0$ 种，后面就是 $A-1$ 个数放入 $B+1$ 个空间了，$A$ 类点的贡献为 $(A-A_0)\times\frac{(A+B-1)!}{B!}$，$B,C,D$ 类点贡献不变，则 $ans_A=(A-A_0)\times\frac{(A+B-1)!}{B!}\times{B!}\times{B!}\times\frac{(D+B-1)!}{(B-1)!}=(A-A_0)\times{B}\times(A+B-1)!\times(D+B-1)!$。

2. $ans_B$：对于 $A$ 类点，现在有 $B$ 个挡板,答案为 $\frac{(A+B-1)!}{(B-1)!}$，对于 $B$ 类点，第一个位置有 $(B-B_0)$ 种情况，后面则是 $(B-1)!$ 种情况，对于 $C,D$ 类点来说情况不变，则 $ans_B=(B-B_0)\times(B-1)!\times{B!}\times\frac{(A+B-1)!}{(B-1)!}\times\frac{(D+B-1)!}{(B-1)!}=(B-B_0)\times{B}\times(A+B-1)!\times(D+B-1)!$。

最后答案就是 $ans_A+ans_B$。

记得取模就行(代码应该不用放吧，直接套公式进去就行了)。

由于对每一位都要进行一次 $O(1)$ 的运算判断点的类型，因此复杂度是 $O(n)$ 的。