==================↵
↵
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 ↵
↵
+ https://www.spoj.com/problems/PR003004/en/↵
+ 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 ↵
↵
+ https://vjudge.net/problem/CodeForces-1036C/origin↵
+ Chill problem standard easy↵
↵
+ https://vjudge.net/problem/CodeForces-628D/origin↵
+ 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↵
↵
+ https://www.codechef.com/problems/DGTCNT ↵
+ 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.↵
↵
+ https://vjudge.net/problem/CodeForces-1073E↵
↵
↵
↵
↵
## Theory↵
↵
- Dp digit template is something like this:↵
↵
```cpp↵
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. $$\text{Answ}(L,R)=\text{Answ}(0,R)-\text{Answ}(0,L)$$↵
↵
2. If you dp digit allow the numbers to move around, fix the segment `l - r` its goona be in making it much easier↵
↵
## Ideas↵
↵
### [Gym 100886 G](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↵
↵
### [SPOJ PR003004](https://www.spoj.com/problems/PR003004/en/)↵
↵
- This problem is a little bit complicated, because we must store `(current sum, total number)`↵
- Formula:↵
↵
$$↵
\text{answ.sum} += i \cdot \text{total\_number} + \text{current\_sum}↵
$$↵
↵
$$↵
\text{answ.number} += \text{total\_number}↵
$$↵
↵
### [Codeforces 1036C](https://vjudge.net/problem/CodeForces-1036C/origin)↵
↵
- Chill problem standard easy↵
↵
### [Codeforces 628D](https://vjudge.net/problem/CodeForces-628D/origin)↵
↵
- 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)↵
↵
### [CSES 2220](https://vjudge.net/problem/CSES-2220/origin)↵
↵
- standard no comment↵
↵
### [CodeChef DGTCNT](https://www.codechef.com/problems/DGTCNT)↵
↵
- 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] = a_0 \text{ OR } cnt[1] = a_1 \text{ OR } \dots \text{ 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.↵
↵
### [Codeforces 1073E](https://vjudge.net/problem/CodeForces-1073E)↵
↵
- standard store mask of all the one that has appeared↵
↵
### [USACO 1307](https://usaco.org/index.php?page=viewproblem2&cpid=1307&lang=en)↵
↵
- very fun problem indeed, instead of normal dp digit, we use the tight logic again↵
- consider `dp[l][r][cmp]` where a segment cover `l -> r` of digit `B`↵
↵
- why can we do this? : Because when fix the position we add the number to then the number wont get moved and we dont need to worry about position anymore (**GREAT TRICK**)↵
- so now we can consider the boolean expression when add `a_i` to left or right of a segment `l - r`↵
↵
- consider a general formula↵
↵
- function `g(x,y)` definition: (this function is used in order to mark the number much easier)↵
↵
```cpp↵
if (x > y) return 2;↵
if (x == y) return 1;↵
if (x < y) return 0;↵
```↵
↵
- function `f(x,y)` definition: (this function is used to merge to `cmp` toghether):↵
↵
```cpp↵
if (x == 0 or (x == 1 and y == 0)) return 0;↵
if (y == 1 && x == 1) return 1;↵
else return 2;↵
```↵
↵
- So for every number we add into this each segment and max using thif function formula, and update `dp[l][r][mask]`↵
- So the answer after is `dp[0][n-1][mask : 0 -> 1] + every lower segment starting at 0`↵
- the segment must start at `0` because when we update we add to every `dp[i][i][comp(current number, target[i])]`, so therefore there would be at least 1 copy at every position `i`↵
↵
### [USACO 1115](https://usaco.org/index.php?page=viewproblem2&cpid=1115&lang=en)↵
↵
- Ideas Look Horrifying at first with the weird formula but we can rephrase the ugly formula using this↵
- THe formula means that every position in two number `x_i` and `y_i` in base-3 must have same parity↵
- we can rewrite `(x_i, y_i)` as `(x_i, x_i + some number)`↵
- Note this work because if `(x_i, y_i)` is on then `(y_i, x_i)` would also be on↵
- when we addition on bit, the `bit[x]` must not be equal to base, if the `bit[x] == 0` then every number would work↵
- when we consider `bit[x]` of the `SomeNumber` part in `(x_i, x_i + some number)`, if after we add all the smaller bit, the current:↵
↵
$$↵
(\text{bit}[x] + \text{carryover}) \bmod 3 \ne 0↵
$$↵
↵
we can fix the number and continue on with the addition so the problem become much more simpler↵
↵
- the problem now become, given `L - R` find `L <= x <= R` where `x` has some position equal to the position we just fixed above
