【数位dp】bzoj1799: [Ahoi2009]self 同类分布

各种奇怪姿势的数位dp

Description

给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

Sample Input

10 19

Sample Output

HINT

【约束条件】1 ≤ a ≤ b ≤ 10^18

题目分析

好像10^18左右的数位dp都是乱搞就好了

既然是要求整除原数，那么数位之和肯定要放进状态里，并且枚举数位总和地去dp。

看上去好像$f[i][j]$表示后面$i$位总和为$j$的合法方案数不就好了吗？

考虑这种状态的转移会发现，从后面做上来不可行啊，没办法处理在开头加上一个数后，能整除数位之和的方案。并且我们启发性地发现，为了转移的合法性，需要在状态里加上余数来限制状态（因为当前不能整除的或许后面能够整除了；反之亦有可能）。

于是想到用$f[i][j][k][done(0/1)]$表示前$i$位和为$j$，除数位总和$sum$的余数为$k$，是否达到上限（done=1表示达到）的合法状态数。

最终答案显然是$\sum{f[digits][sum][0][0]+f[digits][sum][0][1]}$。当然这个sum是要枚举过去的。

如此，转移也就不难处理了，并且时间复杂度也是正确的（位数最大就18）

 #include<bits/stdc++.h>

 typedef long long ll;

 ll a,b;

 ll f[][][][];

 int digit[];

 ll read()

 {

     char ch = getchar();

     ll num = ;

     bool fl = ;

     for (; !isdigit(ch); ch = getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch = getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 ll solve(ll x)

 {

     for (digit[]=; x; x/=)

         digit[++digit[]] = x%;

     for (int i=; i<=digit[]/; i++)

         std::swap(digit[i], digit[digit[]-i+]);

     int mx = digit[]*;

     ll ret = ;

     for (int sum=; sum<=mx; sum++)

     {

         memset(f, , sizeof f);

         f[][][][] = ;

         for (int i=; i<digit[]; i++)

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

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

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

                         if (f[i][j][k][p])

                             for (int t=; t<=; t++){

                                 if (p&&digit[i+] < t) break;

                                 f[i+][j+t][(*k+t)%sum][p&&digit[i+]==t] += f[i][j][k][p];

                             }

         ret += f[digit[]][sum][][]+f[digit[]][sum][][];

     }

     return ret;

 }

 int main()

 {

     a = read(), b = read();

     printf("%lld\n",solve(b)-solve(a-));

     return ;

 }

END

巴特西