Harmony Pairs

题目描述

Roundgod is obsessive about numbers. Let $S(x)$ be the sum of the digits of xx in decimal notation, $(A,B)$ is a harmony pair if and only if $S(A)>S(B)$. Roundgod is given $N$, and she wants to count the number of harmony pairs $(A,B)$ modulo 10⁹ + 7 satisfying $0\le A\le B\le N$.

输入描述:

The only line of input contains one integer N (1 ≤ N ≤ 10¹⁰⁰).

输出描述:

Output one integer indicating the answer.

输入

100

输出

967

题意

给一个 $N$ 满足几个条件，$(1\le N\le 10^{100})$

1. $S(A)>S(B)$
2. $1<A<B<N$
3. 在 $1$ ~ $n$ 中存在几组不同的 $A，B$

#include<bits/stdc++.h>

#define ll long long
using namespace std;
const int mod = 1e9 + 7;
ll dp[110][2020][3][3];
char s[210];
int bit[210];
int n;

ll dfs(int pos, int sum, bool flaga, bool flagb) {
    if (pos < 0) {
        return sum > 1000;
    }
    if (dp[pos][sum][flaga][flagb] != -1) {
        return dp[pos][sum][flaga][flagb];
    }
    ll ans = 0;
    int aend = flaga ? bit[pos] : 9;
    // a
    for (int i = 0; i <= aend; i++) {
        // b
        int bend = flagb ? i : 9;
        for (int j = 0; j <= bend; j++) {
            ans = (ans + dfs(pos - 1,
                             sum - i + j,
                             flaga && (i == aend),
                             flagb && (j == bend)) % mod) % mod;
        }
    }
    return dp[pos][sum][flaga][flagb] = ans;
}

int main() {
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0; i < n; i++) {
        bit[n - i - 1] = s[i] - '0';
    }
    memset(dp, -1, sizeof(dp));
    printf("%lld\n", dfs(n - 1, 1000, 1, 1));
    return 0;
}