弹珠游戏

Question

问题：有R个红色弹珠，G个绿色弹珠，B个蓝色弹珠（R≤G≤B）数一数排列成一条直线的方式有多少种相邻的两个弹珠颜色不同。

例如R=G=B=2，则答案为30。

我试过使用递归当然还有TLE:

Define r(R,B,G) to be the number of ways of arranging them where the first marble is red. Define b(R,B,G),g(R,B,G) respectively.
Then r(R, B, G) = b(R-1,B,G) + g(R-1,B,G)
And the answer is r(R,B,G) + b(R,B,G) + g(R,B,G)

But we can see that r(R, B, G) = b(B, R, G) ...
So, we just need a function f(x,y,z)=f(y,x−1,z)+f(z,x−1,y)
And the answer is f(x,y,z) + f(y,z,x) + f(z,x,y).

限时2秒

我不认为动态不是 TLE 因为 R, G, B <= 2e5

Answer 1

一些限制递归的东西：

如果R>G+B+1，则无法避免相邻的2个红色。（G>R+B+1 & B>R+G+1 的类似论证。）
如果 R=G+B+1，那么您将红色与非红色交替使用，您的问题就简化为有多少种方式可以排列 G 绿色和 B 黑色 w/o 担心邻接（和因此应该有一个封闭形式的解决方案）。（同样，G=R+B+1 和 B=R+G+1 的类似论证。）

Answer 2

您可以使用对称性来减少递归次数。

例如，如果 (R, G, B) = (30, 20, 10) 并且最后一个弹珠是红色的，那么从这个位置开始的排列数与最后一个弹珠是蓝色的完全一样(R, G, B) = (10, 20, 30).

鉴于 R ≤ G ≤ B 被设置为起始条件，我建议在必要时通过交换三个值来保持这种关系。

这是我想出的一些 Python 代码：

memo = {}
def marble_seq(r, g, b, last):
    # last = colour of last marble placed (-1:nothing, 0:red, 1:green, 2:blue)
    if r == g == b == 0:
        # All the marbles have been placed, so we found a solution
        return 1
    # Enforce r <= g <= b
    if r > g:
        r, g = g, r
        last = (0x201 >> last * 4) & 0x0f  # [1, 0, 2][last]
    if r > b:
        r, b = b, r
        last = (0x012 >> last * 4) & 0x0f  # [2, 1, 0][last]
    if g > b:
        g, b = b, g
        last = (0x120 >> last * 4) & 0x0f  # [0, 2, 1][last]
    # Abort if there are too many marbles of one colour
    if b>r+g+1:
        return 0
    # Fetch value from memo if available
    if (r,g,b,last) in memo:
        return memo[(r,g,b,last)]
    # Otherwise check remaining permutations by recursion
    result = 0
    if last != 0 and r > 0:
        result += marble_seq(r-1,g,b,0)
    if last != 1 and g > 0:
        result += marble_seq(r,g-1,b,1)
    if last != 2 and b > 0:
        result += marble_seq(r,g,b-1,2)
    memo[(r,g,b,last)] = result
    return result

marble_seq(50,60,70,-1)  # Call with `last` set to -1 initially

(Result: 205435997562313431685415150793926465693838980981664)

对于高达 2×10⁵ 的值，这可能仍然不够快，但即使有数百个值，结果也非常庞大。您确定您正确地陈述了问题吗？也许你应该给结果模一些素数？

弹珠游戏

The game with the marbles

math

recursion

dynamic