계수 훈련 중의 하나

https://www.luogu.org/problem/P2606
왜 이 문제가 디지털 dp에 있는지 모르겠어요.
분석또 하나의 배열과 관련된 계수 문제인데,
P(i)>P(i/2) 이 조건이 중요해요.
*P(2*i)>P(i)**도 있습니다.
*P(2*i+1)>P(i)**도 있음
이런 두 배의 관계는 두 갈래 나무와 함께 고려해야 한다
두 갈래 나무: i의 왼쪽 아들은 2i, i의 오른쪽 아들은 2i+1
그리고 이 두 갈래 나무는 완전 두 갈래 나무예요.
우선 i개 노드의 완전한 두 갈래 나무에서
루트 노드의 왼쪽 트리에 포함된 노드 수 l, 오른쪽 트리에 포함된 노드 수 r.
먼저 루트 노드의 값은 최소값이어야 합니다.나머지 i-1 노드를 고려합니다.
쉽게 생각할 수 있지만,
이 i-1개 노드에서 l개 노드를 왼쪽 트리로 선택하고 나머지 r개 노드를 오른쪽 트리로 선택할 수 있습니다.그래서 이동:
f[i]=C(i-1,l)×f[l]×f[r]
code by std(코드가 보기 싫지만 정말 또렷):

#include 
#include 
#include 
#include 
#include 
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int N = 1e6 + 5;
int n, PYZ, f[N], fac[N], Log[N], inv[N];
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % PYZ;
        a = 1ll * a * a % PYZ;
        b >>= 1;
    }
    return res;
}
int C(int x, int y) {
    if (!y) return 1;
    int u = C(x / PYZ, y / PYZ), v = x % PYZ, w = y % PYZ, z;
    if (v < w) z = 0;
    else z = 1ll * (1ll * fac[v] * inv[w] % PYZ) * inv[v - w] % PYZ;
    return 1ll * u * z % PYZ;
}
int main() {
    int i, kx, l = 1, r = 1; n = read(); PYZ = read();
    fac[0] = 1; Log[0] = -1;
    for (i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % PYZ,
        Log[i] = Log[i >> 1] + 1;
    kx = min(PYZ - 1, n); inv[kx] = qpow(fac[kx], PYZ - 2);
    for (i = kx - 1; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % PYZ;
    f[1] = f[2] = 1; f[3] = 2;
    for (i = 4; i <= n; i++) {
        if (i - (1 << Log[i]) + 1 <= (1 << Log[i] - 1)) l++;
        else r++;
        f[i] = 1ll * (1ll * C(i - 1, l) * f[l] % PYZ) * f[r] % PYZ;
    }
    printf("%d
", f[n]);
    return 0;
}