月之谜 (mystery.pas/c/cpp)

【题目描述】

打败了 Lord lsp 之后，由于 lqr 是一个心地善良的女孩子，她想净化 Lord lsp 黑化的心，使他变回到原来那个天然呆的 lsp……

在光之英雄 applepi 的指引下，lqr 来到了月之泉。月之泉的精灵告诉她，想要净化 Lord lsp 的话，就要解出月之泉的谜题。

具体地来说是这样的，定义月之数为能够被其十进制表示下各个数位的和整除的数。

给定整数 L,R，你需要计算出区间[L, R]中有多少个月之数。

lqr 发觉这不是数学竞赛能够解决的问题，于是她又找到了你……所以说你需要帮助她解决这个问题。

【输入格式】

输入文件包含多个测试数据。

每组测试数据占一行，含有两个整数 L 和 R。

输入文件以 EOF 结束。

【输出格式】

对于每组测试数据，在单独的一行内输出结果。

【样例输入】

1 100

101 200

【样例输出】

33

26

【数据范围与约定】

对于 20% 的数据，1≤L，R≤1000。

对于 100% 的数据，1≤L，R≤2 31 -1。

每个输入文件的测试数据不超过 3000 组。

——————————————我是分割线————————————————————

好题，数位统计DP

这就是著名的数位统计DP，首先把问题转化为calc(1,R)-calc(1,L-1)

一般解题思路是：先DP预处理、再从高到低按位填数

一旦填了一个比上限小的数位，就可以立即通过DP预处理出的值累加答案

f[模][剩余数字数目][剩余数字的和][剩余位的模]=合法方案数

f[S][i][j][k]=∑(f[S][i-1][j-R][(k-pwr[i-1]*R)%S], 0≤R≤9)

边界条件：F[S][0][0][0]=1

【代码】

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #define maxn 100000112 #define F(i,j,k) for(int i=j;i<=k;i++)13 #define M(a,b) memset(a,b,sizeof(a))14 #define FF(i,j,k) for(int i=j;i>=k;i--)15 #define inf 0x7fffffff16 using namespace std;17 int read(){18 int x=0,f=1;char ch=getchar();19 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}20 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}21 return x*f;22 }23 int n,m;24 int f[82][10][82][82],pwr[82][10];;25 int sum,L,R;26 int num[10];27 inline int modabs (int a, int mod) 28 { 29 return ((a % mod)+mod)%mod;30 }31 int run(int p,int sum,int mod,int s,bool e)32 {33 int a,b;34 if(s-sum<0) return 0;35 else if(!e) return f[s][p+1][s-sum][(s-mod)%s];36 else if(p==-1)37 {38 if(sum==s&&mod==0) return 1;39 else return 0;40 }41 else42 {43 int res=0;44 F(d,0,num[p])45 {46 res+=run(p-1,sum+d,(mod+pwr[s][p]*d)%s,s,d==num[p]);47 }48 return res;49 }50 }51 int fcount(int t)52 {53 int a,b;54 if(t==0) return 0;55 int maxx=0;56 while(t){57 num[maxx++]=t%10;58 t/=10;59 }60 int res=0;61 F(i,1,81) res+=run(maxx-1,0,0,i,true);62 return res;63 }64 int main()65 {66 std::ios::sync_with_stdio(false);//cout<
                
                 <
                 
                  <
                  
                   =0;d++)78 {79 f[s][i][j][k]+=f[s][i-1][j-d][modabs(k-pwr[s][i-1]*d,s)];80 }81 }82 while(cin>>L>>R)83 {84 cout<
                   
                    <