E - Rock (Easy)

$N≦300$ と小さいので、すべての $N$ に対しての答えを求めます。
$6$ の倍数の条件は $2$ の倍数かつ $3$ の倍数であることです。また、それぞれの倍数判定法は以下であることが知られています。

• $2$ の倍数 : 末尾が $2$ の倍数である
• $3$ の倍数 : 桁和が $3$ の倍数である

以下のような方針で2つの情報をもちながらDPをすることが出来ます。

$dp[i][j][k] :=$ $i$ 桁を決定したときの桁和が $j$ 、末尾の偶奇が $k$ ($0$ or $1$) の数
とします。

遷移は $0～9$ を選ぶ $10$ 通りあります。($i=0$の時、$0$ を選ぶ遷移はないことに注意してください)。

遷移は以下のようになります。
$dp[i+1][j+l][lmod2] += dp[i][j][k]$ (ここで $0≦l≦9$ )

$n$ 桁の場合の答えは $dp[n]$ の $j$ が $3$ の倍数であり、$k=0$ であるもののすべての $j×dp[n][j][k]$ の和です。 計算量は $O(N^2)$ です。

mod = 10**9 + 7
m = 305
dp = [[[0 for k in range(2)]for j in range(m * 10 + 10)]for i in range(m + 1)]
A = [0] * m

dp[0][0][0] = 1
for i in range(m):
    for j in range(m * 10 + 10):
        for k in range(2):
            if(dp[i][j][k] != 0):
                for l in range(10):
                    if(i == 0 and l == 0): continue
                    ni = i + 1
                    nj = j + l
                    dp[ni][nj][l%2] += dp[i][j][k]
    a = 0
    for j in range(m*10+10):
        if(j % 3 == 0):
            a += j * dp[i][j][0]
    a %= mod
    A[i] = a

t = int(input())

for _ in range(t):
    n = int(input())
    print(A[n])

$2$ の倍数の末尾の数字は $0,2,4,6,8$ のいずれかであるため、末尾の桁から数字を決定していくと、二次元DPにすることができます。 $n=1$ の時に注意してください。

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
ll mod = 1'000'000'007;

int main() {

    int maxN = 300;
    vector<vector<ll>> dp(maxN + 1, vector<ll>(maxN * 9, 0));
    vector<ll> ans(maxN + 1, 0);
    for (int i = 0; i <= 8; i += 2) dp[1][i] = 1;
    ans[1] = 6;

    for (int i = 2; i <= maxN; i++) {
        for (int j = 0; j < maxN * 9; j++ ) {
            for (int k = 1; k < 10; k++){
                if (j - k >= 0) dp[i][j] += dp[i - 1][j - k];
            }
            
            if (j % 3 == 0) ans[i] += dp[i][j] * j % mod;

            dp[i][j] += dp[i - 1][j];
            dp[i][j] %= mod;
        }
        ans[i] %= mod;
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int n;
        cin >> n; 

        cout << ans[n] << endl;
    }
}