Luogu p1836 number page solution

Luogu P1836 Page number Answer key

Topic link ：P1836 Page number

The question ：

The page number of a book is from $1\sim n$ Consecutive integer of number ：$1,2,3,\cdots ,n$. Please find the sum of all the individual numbers in all the pages , For example $123$ page , Its sum is $1+2+3=6$.

$1\le n\le 10^9$

It is easy to find that this thing can be transformed into

$1\sim n$ How many numbers are there in each number

Consider digits dp, See link

Then multiply each number by one

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int x,mi[25],cnt[25],num[25],f[25];
void solve(int x,int *cnt)
{
    
    int len=0;
    memset(num,0,sizeof(num));
    while(x)
    {
    
        num[++len]=x%10;
        x/=10;
    }
    for(int i=len; i>=1; i--)
    {
    
        for(int j=0; j<=9; j++)
            cnt[j]+=f[i-1]*num[i];
        for(int j=0; j<num[i]; j++)
            cnt[j]+=mi[i-1];
        int res=0;
        for(int j=i-1; j>=1; j--)
        {
    
            res = res * 10 + num[j];
        }
        cnt[num[i]]+=res+1;
        cnt[0]-=mi[i-1];
    }
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    mi[0]=1;
    for(int i=1; i<=18; i++)
    {
    
        f[i]=f[i-1]*10+mi[i-1];
        mi[i]=10*mi[i-1];
    }
    cin >> x;
    solve(x,cnt);
    int res=0;
    for(int i=0; i<=9; i++)
        res+=cnt[i]*i;
    cout << res << '\n';
    return 0;
}

Reprint please explain the source