题解 | 小红的好排列

import sys
n = int(input())
N = n // 3
n_2 = n // 2
MOD = 1000000007
def order(n0, n1):
    res = 1
    for i in range(n0, n1, -1):
        res = (res * i) % MOD
    return res
# def order(k):
#     res = 1
#     for i in range(1, k+1):
#         res *= i
#     return res
if N * 2 < (n_2):
    print(0)
else:
    # print(order(n-N)**2 * order(N)**2 / order(2*N - n_2) / order(n_2) / order(n_2 - N)**2)
    print(order(N, n_2-N)**2 * order(n-N, 2*N -n_2) * order(n-N, n_2)% MOD)

满足被3整除的位置由a_i和i决定

• 第i=3k的位置一定被3整除，因此固定有n//3个元素是满足条件的，n-n//3是不满足的。技巧是利用被3整除的a_i的值移动到需要位置。
• 当a_i//3=0时，对应位置也被整除，所以需要将这n/2-n//3个a_i挪至n-n//3个i!=3k的位置，使得被3整除的个数达到总数目的一半

所以解的个数可以由

• 将这些a_i挪至i!=3k的位置 : 一共需要挪n/2-n//3组合数为C(n-n//3, n/2-n//3)
• 多出的2*n//3-n/2个a_i需要处于i=3k的位置：需要选择C(n/3, 2*n//3-n/2)位这个组合数也可以写成 C(n/3, n/2-n/3)
• 已经选择了n//3个a_i的位置，直接排列：A(n/3, n/3)
• 剩下的n-n//3的a_i排列：A(n-n/3, n-n/3)

代码中实现将一些阶乘组合了起来。