Leetcode 6107. 不同骰子序列的数目

一道比较经典的dp题，感觉可以数位dp直接做，直接推状态和状态转移方程也行。
时间复杂度: $O(n\ast 6\ast 6\ast 6)$

状态:
$dp[i][j][k]$

状态转移方程:

dp[i][j][k]=sum(dp[i-1][l][k])  [gcd(l,k)==1&&l!=k]

边界条件:

dp[2][i][j] = 1 [gcd(i,kj)==1&&l!=k]

当$n==1$直接特判返回就行。

代码实现：

class Solution
{
public:
    const int mod = 1e9 + 7;
    int dp[100007][7][7];
    int distinctSequences(int n)
    {
        if (n == 1)
        {
            return 6;
        }
        int ans = 0;
        for (int i = 1; i <= 6; i++)
        {
            for (int j = 1; j <= 6; j++)
            {
                if (i == j || __gcd(i, j) != 1)
                    continue;
                dp[2][i][j] = 1;
            }
        }
        for (int i = 3; i <= n; i++)
        {
            for (int j = 1; j <= 6; j++)
            {
                for (int k = 1; k <= 6; k++)
                {
                    if (j == k || __gcd(j, k) != 1)
                        continue;
                    for (int l = 1; l <= 6; l++)
                    {
                        if (l == k || l == j || __gcd(l, k) != 1)
                            continue;
                        dp[i][j][k] += dp[i - 1][k][l];
                        dp[i][j][k] %= mod;
                    }
                }
            }
        }
        for (int i = 1; i <= 6; i++)
        {
            for (int j = 1; j <= 6; j++)
            {
                if (i == j || __gcd(i, j) != 1)
                    continue;
                ans += dp[n][i][j];
                ans %= mod;
            }
        }
        return ans;
    }
};