- Define precisely what one DP state represents.
- Establish the base cases before transitions are evaluated.
- Process states in dependency order and combine only already-known values.
Code notes
- 81 lines of Go from the credited upstream file 95D.go.
- The implementation visibly relies on sequence storage, cached states.
- No explicit loop blocks detected.
Complexity
Multiply the number of reachable states by the work performed for each transition, then include the stored state table in memory usage.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1package main2 3import (4 . "fmt"5 "io"6 "slices"7)8 910func cf95D(in io.Reader, out io.Writer) {11 const mod = 1_000_000_00712 const mx = 100113 pow10 := [mx]int{1}14 for i := 1; i < mx; i++ {15 pow10[i] = pow10[i-1] * 10 % mod16 }17 18 var T, k int19 var s []byte20 Fscan(in, &T, &k)21 dp := make([][mx]int, k+1)22 var f func(int, int, int, bool) int23 f = func(i, left, ok int, isLimit bool) (res int) {24 if i < 0 {25 return ok26 }27 if !isLimit {28 if ok > 0 {29 return pow10[i+1]30 }31 p := &dp[left][i]32 if *p > 0 {33 return *p - 134 }35 defer func() { *p = res + 1 }()36 }37 38 up := 939 if isLimit {40 up = int(s[i] - '0')41 }42 for d := range up + 1 {43 if d == 4 || d == 7 {44 newOk := 045 if ok > 0 || left > 0 {46 newOk = 147 }48 res += f(i-1, k, newOk, isLimit && d == up)49 } else {50 res += f(i-1, max(left-1, 0), ok, isLimit && d == up)51 }52 }53 res %= mod54 return55 }56 57 for range T {58 Fscan(in, &s)59 slices.Reverse(s)60 ans := mod - f(len(s)-1, 0, 0, true)61 62 pre := -k - 163 for i, b := range s {64 if b == '4' || b == '7' {65 if i-pre <= k {66 ans++67 break68 }69 pre = i70 }71 }72 73 Fscan(in, &s)74 slices.Reverse(s)75 ans += f(len(s)-1, 0, 0, true)76 Fprintln(out, ans%mod)77 }78}79 8081