HDU 4321 Arcane Numbers 2

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4321

-------------------------------------------------------------------------------

虽然有更优美的做法不过数据范围还是可以数位$DP$的

即把模型转化为在区间内 $mod\ a = b\ mod\ a$ 的数所含$1$的个数之和

四维的数组分别记录枚举到第$x$位是否达到上限 $mod\ a$ 的余数当前位是否为$1$ 这些状态

然后统计在这些状态下的数的个数$F$ 以及在这些状态下的数的总贡献 $G$

转移的话 $F$比较简单

$G$的话先把当前位之后的$G$全部转移上去再把当前位根据$F$的大小算好贡献

之后就是一个记忆化搜索了

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 long long f[][][][], g[][][][], two[];

 int ti[][][][];

 bool num[];

 long long a, b, n, ans;

 int t, len, tt;

 void work(long long x)

 {

     memset(num, , sizeof num);

     len = ;

     while(x)

     {

         num[++len] = x & ;

         x >>= ;

     }

     two[] =  % a;

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

         two[i] = two[i - ] *  % a;

 }

 long long dfs(int x, bool top, int r, bool one)

 {

     if(ti[x][top][r][one] == tt)

         return f[x][top][r][one];

     ti[x][top][r][one] = tt;

     if(x == )

     {

         g[x][top][r][one] = (one && (r == b % a));

         return f[x][top][r][one] = (r == b % a);

     }

     f[x][top][r][one] = g[x][top][r][one] = ;

     if(top)

     {

         if(num[x])

         {

             f[x][top][r][one] += dfs(x - , , (two[x - ] + r) % a, );

             g[x][top][r][one] += g[x - ][][(two[x - ] + r) % a][];

             f[x][top][r][one] += dfs(x - , , r, );

             g[x][top][r][one] += g[x - ][][r][];

         }

         else

         {

             f[x][top][r][one] += dfs(x - , , r, );

             g[x][top][r][one] += g[x - ][][r][];

         }

     }

     else

     {

         f[x][top][r][one] += dfs(x - , , (two[x - ] + r) % a, );

         g[x][top][r][one] += g[x - ][][(two[x - ] + r) % a][];

         f[x][top][r][one] += dfs(x - , , r, );

         g[x][top][r][one] += g[x - ][][r][];

     }

     g[x][top][r][one] += one * f[x][top][r][one];

     return f[x][top][r][one];

 }

 int main()

 {

     scanf("%d", &t);

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

     {

         scanf("%lld%lld%lld", &a, &b, &n);

         work(b);

         ++tt;

         dfs(len + , , , );

         ans = -g[len + ][][][];

         work(b + n * a);

         ++tt;

         dfs(len + , , , );

         ans += g[len + ][][][];

         printf("Case #%d: %lld\n", ca, ans);

     }

     return ;

 }

巴特西

HDU 4321 Arcane Numbers 2

最新文章

热门文章