题目大意

求满足$x \in (t,s] \land x \equiv s (mod\ 3) \land \lnot x$的每一位都是素数的个数，$0 \leq t < s \leq 10^{10^5}$。

解

做过数位$DP$的话就会知道这显然是一道数位$DP$。

$Total$表示满足$x \in (t,s] \land x \equiv s (mod\ 3)$的数的个数。

$F_{i,\ j}$表示满足$x \in [10^{i-1},10^i) \land x \equiv j (mod\ 3)$的数的个数。

初始化$F$:

1. $F_{0,\ 0}=1$;

2. 转移方程: $F_{i,\ j}=\sum F_{i-1,\ (j-Prime)\ Mod\ 3}\ |\ Prime \in \{2,3,5,7\}$;

$DP(n)$为$x \in [1,n] \land x \equiv s (mod\ 3)$的数的个数。

则$Answer=Total-DP(s)+DP(t)$。

$Ps$: 好像还有一个四维的解法.

数位$DP$($DP(n)$)

大概就是:

1. 计算满足$x \in [1,10^{\lfloor log_{10}\,n \rfloor}) \land x \equiv s (mod\ 3)$的数的个数;

2. 计算满足$x \in [10^{\lfloor log_{10}\,n \rfloor},n] \land x \equiv s (mod\ 3)$的数的个数.

还是看代码吧

Code

#include <cstdio>
#include <cctype>
#include <cstring>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)

const int mod=10007,mod3=mod*3,pr[]={2,3,5,7},N=100010;
int f[N][3]={{1}},s[N],t[N],ss,st,sm,tot,tm=1;
char read[N];

inline void get(int *a)
{
    scanf("%s",read),*a=strlen(read);
    rep(i,1,*a)
        a[i]=read[*a-i]-48;
}

inline int dp(int *a)
{
    int ret=0,md=sm;
    rep(i,1,*a-1)
        ret+=f[i][md],ret%=mod;
    repd(i,*a,1)
        rep(j,0,3)
        {
            if (pr[j]>a[i])
                return ret;
            if (pr[j]==a[i])
            {
                md=(9+md-pr[j])%3;
                if (i==1 && !md)
                    return (ret+1)%mod;
                break;
            }
            ret+=f[i-1][(9+md-pr[j])%3],ret%=mod;
            if (j==3)
                return ret;
        }
    return ret;
}

int main()
{
    get(s),get(t);
    rep(i,1,*s)
        sm=(sm+s[i])%3;
    rep(i,1,*s)
        tot+=(s[i]-t[i])*tm+mod3*9,tot%=mod3,tm=tm*10%mod3;
    tot=tot/3+(tot%3>0),tot%=mod;
    rep(i,1,*s)
        rep(j,0,2)
            rep(k,0,3)
                f[i][j]+=f[i-1][(9+j-pr[k])%3],f[i][j]%=mod;
    ss=dp(s),st=dp(t);
    printf("%d\n",(mod+tot-ss+st)%mod);
    return 0;
}

推广$ZZXYY's\ blog$