题目就是说给你一个N。计算一下从0,1,2,3,4,5,,,,,,n-1,n中计算出0,1,2,3,,,,7,8,9分别出现了多少次...
#include<cstdio>
#include<cstring> typedef unsigned __int64 LL; LL dp[11][25][12];
/*
*dp[k][i][j]表示记录目标数字k,第i位取j时，从0位到i位一共有多少个
*/
int bit[25];
LL tenk[22];//10^k
LL n; inline void Init()
{
memset(dp,-1,sizeof dp);
int i;
tenk[0]=1;
for(i=1;i<22;++i)
tenk[i]=tenk[i-1]*10;
} inline int work(LL val)
{
int len=0;
for(;val;val/=10)
bit[++len]=val%10;
return len;
/*
*把val从高位到低位存
*e.g.:val=132,bit=2 3 1
*/
} inline LL dfs(int p,int s,int tar,int u,int e)
{
/*
*直接套用的数位dp模板...
*p: 从高位到低位位置p
*s: 从第一位非0数字开始s=1
*tar: 目标数字
*u: 上一步取u
*e: 边界
*/
if(p<1)
return s&&u==tar;
if(~dp[tar][p][u] && !e && s) return dp[tar][p][u];
/*
*记忆化如果目标数字tar p+1位取u,记忆过。而且s为1
*/
int mx=e?bit[p]:9,i;
LL ret=0;
for(i=0;i<=mx;++i)
{
int news=(s||i>0);
if(i==tar && news)
{
/*
*如果当前位取i而且是目标数字,而且s=1,要两种情况
*如果是边界,而且不是最后一位:加剩下的
*如果不是边界,而且不是最后一位: ret+=10^p-1个数
*->4567 如果目标数字是4而且不是最后一位，当到第4位(从右到左,第4位取4),是边界所以ret要加4567%10^(4-1)==567
*->4567 如果目标数字是4而且不是最后一位，当到第3位(从右到左,第3位取4),不是是边界所以ret要加10^(3-1)==100
*/
if(e&&i==mx)
{
if(p!=1)
ret+=(n%tenk[p-1])+1;
}else if(p!=1)
{
ret+=tenk[p-1];
}
}
ret+=dfs(p-1,news,tar,i,e&&i==mx);
}
if(!e && s) dp[tar][p][u]=ret;
return ret;
} int main()
{
int i;
Init();
while(~scanf("%I64u",&n))
{
int len=work(n);
int ok=0;
for(i=0;i<10;++i)
{
if(ok) putchar(32);
ok=1;
LL ret=dfs(len,0,i,0,1);
if(i==0) ret++;
printf("%I64u",ret);
}
putchar(10);
}
return 0;
}
/*
18446744073699999999 */