题解：P9768 [ROIR 2021 Day 2] A+B

· · 题解

P9768 A+B题解

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

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

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

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

令 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，则依次考虑每个数的情况。

最后答案就是各自相乘为(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。

最后答案就是 ans_A+ans_B。

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

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