NEUQ OJ 2004:追梦之人 (计数数位dp)

2004: 追梦之人

描述

题目描述：

为了纪念追梦人，粉丝们创造了一种新的数——“追梦数”。追梦数要满足以下两个条件：
1、数字中不能出现“7”
2、不能被7整除。
比如：777和4396就不是追梦数，而666是追梦数。现在他们想知道，1到N中有多少个追梦数。

输入：

多组数据。
第一行给出一个正整数T。T为数据组数。
接下来T行，每行包括一个正整数N。
(1 \leq T \leq 10001≤T≤1000) 
(1 \leq N \leq 10^{18}1≤N≤1018)

输出：

对于每组数据，在单独的一行中输出一个整数表示1到N中有多少个追梦数。

样例输入

4
10
14
17
100

样例输出

9
12
14
70

---

当初石乐志要维护三个东西，后来发觉数位只要维护两个东西就好了。
我们的答案是n-被7整除的数-不被7整除但包含7的数。
被7整除的数n/7即可求出。
后面这个写个数位dp即可。
dpi[k]表示长度为i，膜7的余数为j，是否含7的情况为k(k为0表示不含，为1表示含)的数的数量，考虑当前的第i位为x，之前的i-1位组成的数膜7的余数为y，那么dpi+=dpi-1。如果x不是7，那么k应该是0转移到0，1转移到1；如果x是7，那么都转移到k=1。剩下的就是裸的数位dp了。
注意边界。

 #include<bits/stdc++.h>

 #define clr(x) memset(x,0,sizeof(x))

 #define clr_1(x) memset(x,-1,sizeof(x))

 #define mod 7

 #define LL long long

 #define INF 0x3f3f3f3f

 #define mp make_pair

 #define pb push_back

 #define mp make_pair

 #define fi first

 #define se second

 using namespace std;

 const int N=1e5+;

 LL all[][][],num[];

 void init()

 {

     all[][][]=;

     num[]=;

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

         num[i]=(num[i-]*)%mod;

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

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

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

                 if(j!=)

                 {

                     all[i][(int)(j*num[i]%mod+k)%mod][]+=all[i-][k][];

                     all[i][(int)(j*num[i]%mod+k)%mod][]+=all[i-][k][];

                 }

                 else

                      all[i][(int)(j*num[i]%mod+k)%mod][]+=all[i-][k][]+all[i-][k][];

 }

 LL n,m,k;

 LL ans;

 int a[N],t,now;

 bool flag;

 int T;

 int main()

 {

     init();

     scanf("%d",&T);

     while(T--)

     {

         scanf("%lld",&n);

         ans=n-n/;

         m=;

         n++;

         while(n)

         {

             a[++m]=n%;

             n/=;

         }

         now=;

         flag=;

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

         {

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

             {

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

                     if((j*num[i]%mod+k+now)%mod!=)

                     {

                         ans-=all[i-][k][];

                         if(flag || j==mod)

                             ans-=all[i-][k][];

                     }

             }

             now=(now+a[i]*num[i])%mod;

             if(a[i]==mod)

                 flag=;

         }

         printf("%lld\n",ans);

     }

 }