Readme

2318.Number-of-Distinct-Roll-Sequences

我们在基于前i-1位的方案之上，考虑序列的第i位的填充时，思考能否填写某个数字d，需要的约束有：和前一位不能相等，和前一位必须互质，和前两位不能相等。可见，dp[i]关系到了前两位的具体方案。所以我们设计状态dp[i][a][b]，表示前i位里最后两位数字分别是a和b的情况下，所有的合法方案数目。

接下来我们就很容易看出dp[i]与dp[i-1]之间的转移关系。因为i的最后两位是a和b，那么i-1的最后两位必然是某个数x和a。所以我们枚举所有合法的x使得dp[i]能将b接在dp[i-1]之后，要使得xab合法需要的条件是：

1. a和x不能相等
2. b和x不能相等
3. x和a必须互质 满足这些条件的话，就意味着dp[i][a][b] += dp[i-1][x][a]，即将所有合法的dp[i-1][x][a]方案后面直接加上一个b。

有人会说，这里dp[i][a][b]没有考虑检查a是否和x之前的那个数字相同呀。事实上，dp[i]的合法性是建立在dp[i-1]的基础上的。如果dp[i-1][x][a]代表了合法的方案数目，那么自然就不会存在a与x之前的数字相同的问题。

在实际计算中，我们在更新所有dp[i][a][b]的过程中，可以通过计算ab本身的合法性，来提前跳过一些不合法的dp[i][a][b]