IBM Ponder This #292 · 2022 年 8 月

四名舞者 A、B、C、D 表演 $n$ 个时间单位。舞台每时刻只能是一人在中间，或两人分别在右、左。侧边舞者连续表演 1、2 或 3 个时间单位后，必须由当时不在台上的人替换。中间舞者只能表演一个单位，之后由另一人到中间，或另两人到两侧。舞者不能直接在台上换位置。若两名侧边舞者同时需要替换，下一时刻必须变成一人在中间。

以下八单位例子，上行代表右侧、下行代表左侧；同列相同字母表示该人在中间：

AABDACCC
CCCDABBA

以下例子不合法：A、D 同时退场后 B、C 同时上两侧；A 从左侧直接转到中间；B、D 直接互换两侧，都违反规则：

AABBBADB
BDCCAABD

时长 1、2、8 的合法安排数分别为 16、120、17,342,172。计数很大，均对 N=3141592653 取模。n=128 时的余数为 2,484,449,895。

任务：求 n=2^24=16,777,216 时的安排数模 N。

附加问题：求 n=2^256 时的安排数模 N。

解答

认真尝试后再打开

待补充。