The main idea of the topic

A number \ (n \) is called a graceful number if and only if its digits can be divided into two sets, the sum of the numbers in the two sets is equal. How many graceful numbers can be found in \ ([a,b] \).
\(a,b\leq 10^9\)

Analysis

The exact solution is digital \ (dp \) but I won't.

As the range of \ (a,b \) is coveted, it is considered to print the table in sections.

First of all, we need a faster judgment method: for a number \ (n \), calculate the sum of its digits \ (s \), if \ (s \) is odd, then \ (n \) is not a beautiful number; otherwise, make a \ (0 / 1 \) backpack for \ (n \) digits, if \ (s/2 \) can be made, this number is beautiful.

Count \ (ans[k] \) means the number of graceful numbers in \ (1\sim k*10^6 \). Through the violent program, we can run a total of \ (10 ^ 3 \) \ (ans[k] \). We changed the question \ ([a,b] \) to question \ ([1,b] \) and question \ ([1,a-1] \). Consider asking \ ([1,n] \), first count \ (ans[n/10^6] \) into the answer, and then do the rest violence, and you will be happy with AC. What, you ask me \ (ans[k] \) how to include the answer? Directly paste the number of \ (10 ^ 3 \) typed by violence into the program!

Code

This is a program for typing tables (O3 is only opened locally, in order to get answers quickly):

#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>

int ans = 0;
int len, sum, num[15], ok[47];

int check(int n)
{
    len = sum = 0; while (n) num[++len] = n % 10, n /= 10, sum += num[len];
    if (sum & 1) return 0;
    sum /= 2;
    ok[0] = 1; for (int i = 1; i <= sum; i++) ok[i] = 0;
    for (register int i = 1; i <= len; i++) for (register int j = sum; j >= num[i]; j--) ok[j] |= ok[j - num[i]];
    return ok[sum];
}

int main()
{
    freopen("output", "w", stdout);
    for (register int i = 1; i <= 1000000000; i++)
    {
        ans += check(i);
        if (i % 1000000 == 0) printf("%d,", ans);
    }
    return 0;
}

This is the AC procedure (omitted):

#include <cstdio>
#include <cstring>

const int ANS[1001] = {...};

int len, sum, num[15], ok[47];
int check(int n)
{
    len = sum = 0; while (n) num[++len] = n % 10, n /= 10, sum += num[len];
    if (sum & 1) return 0;
    sum /= 2;
    ok[0] = 1; for (int i = 1; i <= sum; i++) ok[i] = 0;
    for (register int i = 1; i <= len; i++) for (register int j = sum; j >= num[i]; j--) ok[j] |= ok[j - num[i]];
    return ok[sum];
}

int solve(int n)
{
    int k = n / 1000000, ret = ANS[k];
    for (int i = k * 1000000 + 1; i <= n; i++) ret += check(i);
    return ret;
}

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", solve(b) - solve(a - 1));
    return 0;
}

Striking a watch is an art.