9168 - 判断题(judgement)

20pts

暴力枚举。

时间复杂度 $O(n)$

动态规划。

$f[i_1][i_2][i_3][i_4][0/1]$ TT,TF,FT,FF有i1,i2,i3,i4个，最后一位是 T（记为 1）或 F （记为 0）的方案数。

以最后一位是 F 为例： $f[i_1][i_2][i_3][i_4][0] = f[i_1][i_2-1][i_3][i_4][1] + f[i_1][i_2][i_3][i_4-1][0]$ 。

初始值： $f[0][0][0][0][1]=f[0][0][0][0][0]=1$ 。

时间/空间复杂度 $O(p_1p_2p_3p_4)$ 。

考虑最终的字符串一定能划分成形如 TT...T（大于等于 1 个连续的 T）和FF...F（大于等于 1 个连续的 F）拼凑而成的形式。

TF 只会出现在 TT...T 和 FF...F 的交界处，FT 只会出现在 FF...F 和 TT...T 的交界处，而 TT 和 FF 只会分别出现在 TT...T 和 FF...F 的内部。

最终的字符串只会有以下四种可能：

因为 TT...T 和 FF...F 的数量最多相差 $1$ ，所以 TF 和 FT 的数量最多相差 $1$ ，否则必然无解。

当 TT...T 和 FF...F 的数量相差 $1$ 时，对应 1 或 2 两种情况。

以情况 1 为例，此时 TT...T 的数量等同于 TF 的数量加上 $1$ ，FF...F 的数量等同于 FT 的数量。

TT 的数量代表了在所有 TT...T 中还要放进多少个 T。举例说明：

T 中有 $0$ 个 TT，TT 中有 $1$ 个 TT，TTT 中有 $2$ 个 TT……

如果只考虑 T，那么就是将 $(p_1+p_2+1)$ 个 T 分成 $p_2$ 段，相当于将 $(p_1+p_2+1)$ 个放成一排的球分成 $p_2$ 段，要求每段至少有一个球的方案数。

这相当于在 $(p_1+p_2)$ 个空隙放入 $p_2$ 个隔板，方案数为 $\binom{p_1+p_2}{p_2}$ （这是组合数的一种表示）。

类似地，对于 F，方案数为 $\binom{p_3+p_4-1}{p_3}$ 。（因为此时有 $(p_3+p_4)$ 个 F）

由于 T 如何放入对于 F 是没有影响的，并且可以保证产生不同的方案，所以总方案数为 $\binom{p_1+p_2-1}{p_2} \binom{p_3+p_4}{p_3}$ 。

当 TT...T 和 FF...F 的数量相等时，对应 3 和 4 两种情况。

这时，第一段可能是 TT...T（此时 $(p_2+1)$ 个 TT...T， $p_3$ 个 FF...F），也可能是 FF...F（此时 $p_2$ 个 TT...T， $(p_3+1)$ 个 FF...F）。计算方法与上文类似。

时间复杂度 $O(n^2)$ 或 $O(n\log n)$ 。