This blog is my personal reflection on what I have learned in Dp Digit
Theory: + Dp digit template is something likethis void dfs(pos, tight, [some conditions], target) if pos == target: return something limit = if tight = true — > target[pos] else 9 (may vary depending on problem) for i : 0 — > limit: update_tight() answ += do something() dp[pos][tight][some condition] = answ return answ
Trick: 1. Answ(L, R) = Answ(0,R) — Answ(0, L)
- Ideas:
- https://codeforces.me/gym/100886/problem/G
- this problem mentioned max, which mean you can't use trick 1
- so we must keep a low_tight for keeping the number >= L, and a high_tight to keep a number <= R
- and then you just keep max number for each state simple
- Be careful on the limit because you might be off by one
- This problem is a little bit complicated, because we must store (current sum, total number)
- Formula : answ.sum += i * total_number + current_sum
- answ.number += total_number
- Chill problem standard easy
- Problem require 2 requirment:
- A mutiple of M
- appear D ONLY ON even position
for the mod requirement just store mod of M very simple
- The even requirement is a bit hard but it is possible, just store the current parity of the position (stays odd until started)
vjudge.net/problem/CSES-2220/origin
- standard no comment
- Not really dp digit because contain a lot of combinatorics but it contain dp digit idea
- so first we have a bunch of requiremnt, which require cnt[0] == a0 OR cnt[1] == a1 OR ... cnt[9] == a[9]
- This is clear inclusion exclusion. So we must run through every mask (complexity 2^10)
- the idea for this problem is to walk on tight
- the moment tight turn off it never turns on again which mean the moment the tight turn off we use combinatorics to count (ways to shuffle the numbers in mask * number of ways to shuffle the number not in mask)
Precaculate Combinatoric also be careful with 0 it will mess your program up.
