【BZOJ】1833: [ZJOI2010] count 数字计数(数位dp)

题目

传送门:QWQ

分析

蒟蒻不会数位dp,又是现学的

用$ dp[i][j][k] $ 表示表示长度为i开头j的所有数字中k的个数

然后预处理出这个数组,再计算答案

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[][][], ans[], b[], sum[];
int solve(ll x,ll d){
int len=; ll bef=x;
for(;x;x/=){ b[++len]=x%; }
for(int i=;i<len;i++)
for(int j=;j<;j++){
for(int k=;k<;k++) ans[k]+=dp[i][j][k]*d;
}
for(int i=len;i>;i--){
for(int j=;j<b[i];j++){
if(!j&&len==i) continue;// 最高位不是0打头
for(int k=;k<;k++) ans[k]+=dp[i][j][k]*d;
}
ans[b[i]]+=d*(bef%sum[i]+);
}
}
int main(){
ll aa,bb; scanf("%lld%lld",&aa,&bb);
sum[]=;
for(int i=;i<;i++) sum[i]=sum[i-]*;
for(int i=;i<;i++) dp[][i][i]=; for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++){
for(int l=;l<;l++){
dp[i][j][l]+=dp[i-][k][l];
}
dp[i][k][k]+=sum[i-];//以k为开头的数
}
solve(bb,); solve(aa-,-);
for(int i=;i<;i++) printf("%lld ",ans[i]);
printf("%lld\n",ans[]);
return ;
}
上一篇:wpf图片切换,幻灯效果


下一篇:PAT A1140 Look-and-say Sequence (20 分)——数学题