简单易懂递推dp90分求调
查看原帖
简单易懂递推dp90分求调
1288642
lmn985楼主2025/7/3 10:53
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;
const int N=15;
int l,r,dp[N][N][N],a[N],cnt[N];
int log(int x){
	return (x<10)?1:log(x/10)+1;
}
void cal(int x){
	int len=log(x),I=len-1,nx=x,have[15]={0};
	while(nx)a[I]=nx%10,nx/=10,I--;
	rep(i,0,14)rep(j,0,10)cnt[j]+=dp[len-1][i][j]*i;
	rep(i,0,len){
		cnt[a[i]]++;
		rep(now,(i==0)?1:0,a[i]){
			have[now]++;
			rep(j,0,10){
				if(i<len-1)rep(res,0,len-i)cnt[j]+=dp[len-i-1][res][j]*(res+have[j]);
				else cnt[j]+=have[j];
			}
			have[now]--;
		}
		have[a[i]]++;
	}
}
signed main(){
	rep(i,0,10)dp[1][1][i]=1,dp[1][0][i]=9;
	rep(i,2,14){
		rep(j,0,14){
			rep(k,0,10){
				dp[i][j][k]=dp[i-1][j][k]*9;
				if(j>0)dp[i][j][k]+=dp[i-1][j-1][k];
			}
		}
	}
	cin>>l>>r;
    cal(l-1);
	rep(i,0,10)cnt[i]=-cnt[i];
	cal(r);
	rep(i,0,10)cout<<cnt[i]<<' ';
    return 0;
}
2025/7/3 10:53
加载中...