在一个有向无环图 G 中,给节点分别标上 1,2,…,n 的编号。然后我们有一些小球。小球的移动是有规则的。每个节点都有一个“记忆”,表示上一次小球通过了这个节点去向了几号节点。如果没有小球通过过,“记忆”为 −1。如果某个“时刻” i 号节点有小球,那么下一个“时刻”小球会去向比“记忆”中的节点编号大的且存在一条有向边 i→j 的 j 号节点。如果没有比“记忆”中的节点编号大的可到达的节点,就重新从可到达的编号最小的节点开始。如果当前节点有小球,且没有可到达的节点。那么小球视为被此节点“接受”。小球从第 1 “时刻”开始,每个“时刻”都会在 1 号节点放置一个小球。
可以举个例子,即一个简单的图 1→2。从第 1 时刻开始,每一个时刻 1 号节点上都有一个小球。同时从第 2 个“时刻”开始,每一个“时刻” 2 号节点都会“接受”一个来自 1 号节点的小球。
再比如说一个图 1→2,1→3,这个时候 1 号节点给出的球会在 2 号节点和 3 号节点之间“反复横跳”,并被“接受”。如果是图 1→2,1→3,2→3,可以得到 3 号节点从第 2 个“时刻”开始,每奇数个“时刻”会“接受” 2 个小球,偶数个时刻不接受小球。
我的问题是,能否编写比较快速的程序,能够预测第 T 时刻每个节点“接受”的小球数量?或者有没有数学方法可以得到答案?如果有这样的题目(不要类似,要一模一样),我也可以去看题解的。