codeforce 1073E. Segment Sum

看到这个就是数位DP了，然而细节极多，对于i=1状态直接判了，还有最后一位直接算了

设f[i][zt][0/1]表示枚举到第i位，用了那些数字，是否有前导0（前导0不计入数字，否则就不知道后面有没有0了）的数的和，g是数的个数

转移看代码

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL mod=;

int K,n,a[];

LL mi[],f[][][],g[][][];int o[];

LL calc(LL G)

{

    memset(a,,sizeof(a));n=;

    LL d=G;

    while(d>)a[++n]=d%,d/=;

    LL ret=;int z=;d=;

    for(int i=n;i>=;i--)

    {

        d=(d*)%mod;

        for(int k=;k<a[i];k++)

        {

            LL t=ret;

            if(k==&&i==n)

            {

                for(int zt=(<<)-;zt>=;zt--)

                    if(o[zt]<=K)

                    {

                        ret=(ret+f[i-][zt][]+f[i-][zt][])%mod;

                    }

            }

            else

            {

                for(int zt=(<<)-;zt>=;zt--)

                {

                    if(o[zt|z|(<<k)]<=K)

                        ret=(ret+(mi[i-]*(d+k)%mod*g[i-][zt][]%mod)+f[i-][zt][])%mod;

                    if(o[zt|z|(<<k)|]<=K)

                        ret=(ret+(mi[i-]*(d+k)%mod*g[i-][zt][]%mod)+f[i-][zt][])%mod;

                }

            }

            int p;p++;

        }

        z|=(<<a[i]);d=(d+a[i])%mod;

    }

    for(int k=;k<=a[];k++)

        if(o[z|(<<k)]<=K)ret+=(d*+k)%mod;

    return ret;

}

int main()

{

    mi[]=;for(int i=;i<=;i++)mi[i]=mi[i-]*%mod;

    memset(f,,sizeof(f));

    memset(g,,sizeof(g));

    g[][][]=;

    for(int k=;k<=;k++)f[][<<k][]=k,g[][<<k][]=;

    for(int i=;i<=;i++)

        for(int zt=(<<)-;zt>=;zt--)

        {

            f[i][zt][]=(f[i][zt][]+f[i-][zt][]+f[i-][zt][])%mod;

            g[i][zt][]=(g[i][zt][]+g[i-][zt][]+g[i-][zt][])%mod;

            //k==0;

            for(int k=;k<=;k++)

                if(zt&(<<k))

                {

                    f[i][zt][]=(f[i][zt][]+(mi[i-]*k%mod*g[i-][zt^(<<k)][]%mod)+f[i-][zt^(<<k)][])%mod;

                    g[i][zt][]=(g[i][zt][]+g[i-][zt^(<<k)][])%mod;

                    f[i][zt][]=(f[i][zt][]+(mi[i-]*k%mod*(g[i-][zt][])%mod)+f[i-][zt][])%mod;

                    g[i][zt][]=(g[i][zt][]+g[i-][zt][])%mod;

                    if(zt&)

                    {

                        f[i][zt][]=(f[i][zt][]+(mi[i-]*k%mod*(g[i-][zt^(<<k)][]+g[i-][zt^(<<k)^][])%mod)+f[i-][zt^(<<k)][]+f[i-][zt^(<<k)^][])%mod;

                        g[i][zt][]=(g[i][zt][]+g[i-][zt^(<<k)][]+g[i-][zt^(<<k)^][])%mod;

                        f[i][zt][]=(f[i][zt][]+(mi[i-]*k%mod*(g[i-][zt][]+g[i-][zt^][])%mod)+f[i-][zt][]+f[i-][zt^][])%mod;

                        g[i][zt][]=(g[i][zt][]+g[i-][zt][]+g[i-][zt^][])%mod;

                    }

                }

        }

    memset(o,,sizeof(o));

    for(int zt=(<<)-;zt>=;zt--)

        for(int k=;k<=;k++)

            if(zt&(<<k))o[zt]++;

    LL L,R;

    scanf("%lld%lld%d",&L,&R,&K);

    printf("%lld\n",((calc(R)-calc(L-))%mod+mod)%mod);

    return ;

}