Yukicoder No.220 世界のなんとか2

solution

$i$桁以下の数で、文字3を含むかどうかが$j \in \{ \mathrm{T}, \mathrm{F} \}$で、割った余り$k \lt 3$、であるような整数の数を$\mathrm{dp}(i,j,k)$とするDP。$O(p)$。

関数$\mathrm{dp} : \mathbb{N} \times 2 \times 3 \to \mathbb{N}$は、数の$10$進展開の先頭にひとつ数字を付け加えたとき、それらの分類がどのように遷移するかで定義する。

implementation

時間に追われて書いた。焦りの跡が見える。

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
typedef long long ll;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
int main() {
    int p; cin >> p;
    vector<vector<vector<ll> > > dp = vectors(p+1, 2, 3, ll());
    dp[0][0][0] = 1;
    repeat (i,p) {
        dp[i+1][1][0] =
            + dp[i][1][0] * 4 /* 0, 3, 6, 9 */
            + dp[i][1][1] * 3 /* 2, 5, 8 */
            + dp[i][1][2] * 3 /* 1, 4, 7 */
            + dp[i][0][0]; /* 3 */
        dp[i+1][1][1] =
            + dp[i][1][0] * 3 /* 1, 4, 7 */
            + dp[i][1][1] * 4 /* 0, 3, 6, 9 */
            + dp[i][1][2] * 3 /* 2, 5, 8 */
            + dp[i][0][1]; /* 3 */
        dp[i+1][1][2] =
            + dp[i][1][0] * 3
            + dp[i][1][1] * 3
            + dp[i][1][2] * 4
            + dp[i][0][2]; /* 3 */
        dp[i+1][0][0] =
            + dp[i][0][0] * 3  /* 0,    6, 9 */
            + dp[i][0][1] * 3  /* 2, 4, 7 */
            + dp[i][0][2] * 3; /* 1, 5, 8 */
        dp[i+1][0][1] =
            + dp[i][0][0] * 3
            + dp[i][0][1] * 3 /* 0,    6, 9 */
            + dp[i][0][2] * 3;
        dp[i+1][0][2] =
            + dp[i][0][0] * 3
            + dp[i][0][1] * 3
            + dp[i][0][2] * 3; /* 0,    6, 9 */
    }
    ll ans =
        + dp[p][1][0]
        + dp[p][1][1]
        + dp[p][1][2]
        + dp[p][0][0]
        - 1; // 0
    cout << ans << endl;
    return 0;
}