链接:
https://www.luogu.com.cn/problem/P2602
和上题一样~
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 23; int a[N]; ll f[N][2]; ll sf[N][2][N]; ll ct[N]; ll tct[N]; ll dfs(int pos, int lit, int begin){ if(pos == 0) return 1; if(f[pos][begin] != 0 && !lit){ for(int i = 0; i <= 9; i++){ ct[i] += sf[pos][begin][i]; } return f[pos][begin]; } ll ret = 0; int high = lit ? a[pos] : 9; ll oct[N]; for(int i = 0; i <= 9; i++){ oct[i] = ct[i]; } for(int i = 0; i <= high; i++){ ll temp; temp = dfs(pos - 1, lit && i == high, begin || i != 0); if(begin || i != 0) { ct[i] += temp; ret += temp; } } if(!lit){ for(int i = 0; i <= 9; i++){ sf[pos][begin][i] = ct[i] - oct[i]; } f[pos][begin] = ret; } return ret; } void work(ll n){ memset(f, 0, sizeof f); memset(sf, 0, sizeof sf); memset(ct, 0, sizeof ct); int cnt = 1; while(n > 0){ a[cnt++] = n % 10; n/=10; } dfs(cnt - 1, 1, 0); } int main(){ ll a,b; cin>>a>>b; work(a - 1); for(int i = 0; i <= 9; i++){ tct[i] = ct[i]; } work(b); for(int i = 0; i <= 9; i++){ printf("%lld ", ct[i] - tct[i]); } }