题目链接:
-------------------------------------------------------------------------------
虽然有更优美的做法 不过数据范围还是可以数位$DP$的
即把模型转化为 在区间内 $mod\ a = b\ mod\ a$ 的数所含$1$的个数之和
四维的数组分别记录 枚举到第$x$位 是否达到上限 $mod\ a$ 的余数 当前位是否为$1$ 这些状态
然后统计在这些状态下的数的个数$F$ 以及在这些状态下的数的总贡献 $G$
转移的话 $F$比较简单
$G$的话先把当前位之后的$G$全部转移上去 再把当前位根据$F$的大小算好贡献
之后就是一个记忆化搜索了
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 long long f[50][2][10010][2], g[50][2][10010][2], two[50]; 7 int ti[50][2][10010][2]; 8 bool num[50]; 9 long long a, b, n, ans;10 int t, len, tt;11 void work(long long x)12 {13 memset(num, 0, sizeof num);14 len = 0;15 while(x)16 {17 num[++len] = x & 1;18 x >>= 1;19 }20 two[0] = 1 % a;21 for(int i = 1; i < len; ++i)22 two[i] = two[i - 1] * 2 % a;23 }24 long long dfs(int x, bool top, int r, bool one)25 {26 if(ti[x][top][r][one] == tt)27 return f[x][top][r][one];28 ti[x][top][r][one] = tt;29 if(x == 0)30 {31 g[x][top][r][one] = (one && (r == b % a));32 return f[x][top][r][one] = (r == b % a);33 }34 f[x][top][r][one] = g[x][top][r][one] = 0;35 if(top)36 {37 if(num[x])38 {39 f[x][top][r][one] += dfs(x - 1, 1, (two[x - 1] + r) % a, 1);40 g[x][top][r][one] += g[x - 1][1][(two[x - 1] + r) % a][1];41 f[x][top][r][one] += dfs(x - 1, 0, r, 0);42 g[x][top][r][one] += g[x - 1][0][r][0];43 }44 else45 {46 f[x][top][r][one] += dfs(x - 1, 1, r, 0);47 g[x][top][r][one] += g[x - 1][1][r][0];48 }49 }50 else51 {52 f[x][top][r][one] += dfs(x - 1, 0, (two[x - 1] + r) % a, 1);53 g[x][top][r][one] += g[x - 1][0][(two[x - 1] + r) % a][1];54 f[x][top][r][one] += dfs(x - 1, 0, r, 0);55 g[x][top][r][one] += g[x - 1][0][r][0];56 }57 g[x][top][r][one] += one * f[x][top][r][one];58 return f[x][top][r][one];59 }60 int main()61 {62 scanf("%d", &t);63 for(int ca = 1; ca <= t; ++ca)64 {65 scanf("%lld%lld%lld", &a, &b, &n);66 work(b);67 ++tt;68 dfs(len + 1, 1, 0, 0);69 ans = -g[len + 1][1][0][0];70 work(b + n * a);71 ++tt;72 dfs(len + 1, 1, 0, 0);73 ans += g[len + 1][1][0][0];74 printf("Case #%d: %lld\n", ca, ans);75 }76 return 0;77 }