设f[i][j][p]表示长度为i 最高位为j p出现的个数
显然 f[i][j][p]=sigma{f[i-1][k][p]} 其中k是次高位 但是最高位出现的那么多次都没有被我们算进去
但是很显然只需要加上(i-2)^10就阔以了
然后常规的分[1,b],[1,a-1]解决
常规的分成两部分 一部分最高位小于最高位(似乎有点怪怪的??) 另一部分就是剩下的
在这里只说下另一部分
算了懒得说了 反正就那样 注意特判
#include<bits/stdc++.h> #define ll long long using namespace std; ll a,b,num[20]; ll bin[20],f[20][10][10],res[20]; void solve(ll x,int flag) { int cnt=0; ll x2=x; memset(num,0,sizeof(num)); while(x) num[++cnt]=x,x/=10; for(register int i=1;i<cnt;i++) for(register int j=1;j<=9;j++) for(register int k=0;k<=9;k++) res[k]+=f[i][j][k]*flag; int tmp=cnt; while(tmp) { for(int i=0;i<num[tmp];i++) { if(!i&&tmp==cnt) continue; for(int j=0;j<=9;j++) res[j]+=f[tmp][i][j]*flag; } res[num[tmp]]+=(x2%bin[tmp]+1)*flag; tmp--; } } void init() { bin[1]=1; for(int i=2;i<=14;i++) bin[i]=bin[i-1]*10; for(int i=0;i<=9;i++) f[1][i][i]=1; for(register int i=2;i<=13;i++) //长度 { for(register int j=0;j<=9;j++) //当前最高位 { for(register int k=0;k<=9;k++) //次高位 { for(register int p=0;p<=9;p++) { f[i][j][p]+=f[i-1][k][p]; } f[i][j][j]+=bin[i-1]; //打表后发现最高位都没算 } } } } int main() { init(); cin>>a>>b; if(a>b) swap(a,b); solve(b,1); solve(a-1,-1); for(int i=0;i<=9;i++) cout<<res[i]<<" "; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9914484.html
