我假设您提供的链接中的公式是正确的：

为了避免整数溢出，我们需要应用这些模算术规则：

(a * b) mod c = ((a mod c) * (b mod c)) mod c

(a ± b) mod c = ((a mod c) ± (b mod c)) mod c

将它们应用于公式：

但是我们怎么计算呢

...而不直接计算系数本身（这可能导致溢出）？
由于3是一个质数，这可以通过**Lucas's theorem**来实现：

...其中n_i, m_i是n, m在 base-3 中的第i位。
使用整数除法可以很容易地转换为基数3：

// convert a number to base 3
// and returns the number of digits
unsigned conv_base_3(unsigned n, unsigned max, unsigned* out)
{
    unsigned i = 0;
    while (i < max && n > 0)
    {
        out[i] = n % 3;
        n /= 3;
        i++;
    }
    return i;
}

注意，由于n_i, m_i总是在[0, 2]的范围内（因为它们是以3为基数的数字），所以C(n_i, m_i)非常容易计算：

// calculate the binomial coefficient for n < 3
unsigned binom_max_2(unsigned n, unsigned k)
{
    if (n < k)
        return 0;
    switch (n)
    {
        case 0:
        case 1:
            return 1;
        case 2:
            return 1 + (k == 1);

        // shouldn't happen
        default:
            return 0;
    }
}

现在是定理本身：

// Lucas's theorem for p = 3
unsigned lucas_3(unsigned len_n, const unsigned * dig_n,
                 unsigned len_k, const unsigned * dig_k)
{
    // use modulo product rule:
    // prod[i] % 3 = ((prod[i - 1] % 3) * value[i])      
    unsigned prod = 1;
    for (unsigned i = 0; i < len_n; i++) {
        unsigned n_i = dig_n[i];
        unsigned k_i = (i < len_k) ? dig_k[i] : 0;
        prod = (prod * binom_max_2(n_i, k_i)) % 3;
    }
    return prod % 3;
}

字符转换：

// convert from 012 to RGB
char int_2_char(int i)
{
    switch (i) {
        case 0: return 'R';
        case 1: return 'G';
        case 2: return 'B';

        // shouldn't happen
        default:
            return '\0';
    }
}

// convert from RGB to 012
unsigned char_2_int(char c)
{
    switch (c) {
        case 'R': return 0;
        case 'G': return 1;
        case 'B': return 2;

        // shouldn't happen
        default:
            return 3;
    }
}

最后，三角形算法：

// the problem constraints state that n <= 10 ** 5
// max number of base-3 digits
#define MAX_N_LOG_3 11

// main algorithm function
char triangle(const char * input)
{
    unsigned sum = 0;
    const int n = strlen(input);

    // calculate digits of n - 1
    unsigned dig_n[MAX_N_LOG_3];
    unsigned len_n = conv_base_3(n - 1, MAX_N_LOG_3, dig_n);

    for (unsigned km1 = 0; km1 < n; km1++)
    {
        // calculate digits of k - 1
        unsigned dig_k[MAX_N_LOG_3];
        unsigned len_k = conv_base_3(km1, MAX_N_LOG_3, dig_k);

        // calculate C(n - 1, k - 1) mod 3
        unsigned Cnk_mod3 = lucas_3(len_n, dig_n, len_k, dig_k);

        // add using the modulo rule
        sum = (sum + Cnk_mod3 * char_2_int(input[km1])) % 3;
    }

    // value of (-1) ** (n - 1)
    // no need for pow; just need to know if n is odd or even
    int sign = (n % 2) * 2 - 1;

    // for negative numbers, must resolve the difference
    // between C's % operator and mathematical mod
    int sum_mod3 = (3 + (sign * (int)(sum % 3))) % 3;
    return int_2_char(sum_mod3);
}

上面的代码通过了所有的测试。请注意，它是为了清晰而不是性能而编写的。
那么，为什么这段代码能够在分配的时间内通过所有测试，而简单的基于表的方法却不能呢？因为它的时间复杂度：

• 基于表的方法处理三角形的所有水平，即**O(n^2)**（参见Triangle Numbers）。
• 当然，使用Lucas的算法，只需要处理顶层;然而，算法本身是O(log n)，因为它循环通过n的每个数字（无论基数如何）。总体复杂度是**O(n log n)**，这仍然代表着显着的改进。

const triangle = row => {
  let reduced = row.length > 1 ? '' : row;
  for (let i = 0; i < row.length - 1; i += 1) {
    reduced += row[i] == row[i + 1] ? row[i] : 'RGB'.replace(row[i], '').replace(row[i + 1], '');
  }
  return reduced.length > 1 ? triangle(reduced) : reduced;
}

triangle('B') == 'B'
triangle('GB') == 'R'
triangle('RRR') == 'R'
triangle('RGBG') == 'B'
triangle('RBRGBRB') == 'G'
triangle('RBRGBRBGGRRRBGBBBGG') == 'G'

const triangle = row => {
  let reduced = row.length > 1 ? '' : row;
  for (let i = 0; i < row.length - 1; i += 1) {
    reduced += row[i] == row[i+1] ? row[i] : 'RGB'.replace(row[i], '').replace(row[i+1], '');
  }
  return reduced.length > 1 ? triangle(reduced) : reduced;
}

def triangle(x):
l =len(x)
v=l
R=""

for j in range(v-1):
    for i in range(l-1):
        la=[x[i],x[i+1]]
        if x[i]==x[i+1]:
            R+=x[i]
        else:
            if "R" not in la:
                R+= "R"
            elif "G" not in la:
                R+= "G"
            else:
                R+= "B"
    x=R    
    R=""
    l=len(x)
return (x)

递归在这里没有什么用处，因为你永远不需要返回到以前的状态。迭代是一个更好的解决方案，而且可以相当简单地完成。
对初始字符串的更改也可以就地进行，因为一旦使用和更改了初始值，就不需要返回到原始值。
方法如下。只要字符串大于一个字符，就处理原始字符串中的每组两个字符（重叠）。
对于该对，根据规则更改第一个字符。当所有对都完成时，从字符串中删除最后一个字符，从而使字符串少一个字符。
下面是一些示例代码，其中包含不必要但有用的检查和输出函数：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Helper function to output nicely spaced string.

static void output(int gap, char *str) {
    // Spaces at line start.

    while (gap-- > 0)
        putchar(' ');

    // Actual string with spaces between letters, end line following.

    while (*str != '\0') {
        putchar(' ');
        putchar(*str++);
    }
    putchar('\n');
}

// The meat of the solution.

int main(int argc, char *argv[]) {
    // Check parameter count and content.

    if (argc != 2) {
        fprintf(stderr, "*** Needs one argument\n");
        return 1;
    }

    size_t strSz = strlen(argv[1]);
    if (strSz == 0) {
        fprintf(stderr, "*** Argument too short\n");
        return 1;
    }
    printf("String size is %ld\n", strSz);
    int debug = (strSz <= 20);

    for (char *str = argv[1]; *str != '\0'; str++) {
        if (*str == 'R' || *str == 'G' || *str == 'B')
            continue;
        fprintf(stderr, "*** Bad character '%c' found\n", *str);
        return 1;
    }

    // Continue until you have a short enough string.

    int spaces = 0;
    while (strSz > 1) {
        // Output current string, update spaces for next.

        char *str = argv[1];
        if (debug)
            output(spaces++, str);

        // Process each overlapping pair in string.

        while (*str != '\0') {
            if      (*str == 'G' && *(str + 1) == 'R') *str = 'B';
            else if (*str == 'R' && *(str + 1) == 'G') *str = 'B';
            else if (*str == 'B' && *(str + 1) == 'G') *str = 'R';
            else if (*str == 'G' && *(str + 1) == 'B') *str = 'R';
            else if (*str == 'B' && *(str + 1) == 'R') *str = 'G';
            else if (*str == 'R' && *(str + 1) == 'B') *str = 'G';

            str++;
        }
        *(str - 1) = '\0';
        strSz--;
    }

    // Output final one-character string.

    if (debug)
        output(spaces, argv[1]);
    else
        puts(argv[1]);

    return 0;
}

当使用参数RRGBRGBB运行时，该代码的输出如预期的那样：

String size is 8
 R R G B R G B B
  R B R G B R B
   G G B R G G
    G R G B G
     B B R R
      B G R
       R B
        G

它也适用于字符串的极限（100，000个字符）但请记住它是O（n2）解决方案，因此会随着大小的增大而变慢。对随机100，000个字符的字符串的测试运行在不到15秒的时间内完成，因此，如果需要比这更快，则此解决方案将不适合。为了完整性，下面是我系统上各种输入大小的运行时表（禁用调试输出）：

Input size   Run time
----------   --------
         1    0.001 s
        10    0.002 s
       100    0.002 s
      1000    0.005 s
     10000    0.141 s
    100000   14.331 s

它跨越了一秒的阈值，大约在20，000到30，000个字符之间。