从0,1,2...n中统计0,1,2...9各出现了多少次【SWUN1597】

题目就是说给你一个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^kLL 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*/