题解：P8350 [SDOI/SXOI2022] 进制转换

· · 题解

是个美难题。

第一个想法是假设 y 或 z 为 1 该怎么做。我的想法是拆位去做，若 z=1，则每个数位的贡献是 (1+x^{2i}y)，但是发现这并没有什么卵用，这道题的关键在于如何处理二三进制之间的关系。不过按位处理是必需的，因为这道题一个数的贡献显然可以按位拆贡献，因为位数和在指数就能直接加了。

我尝试设 f(i,j,k,l,0/1) 表示二进制到 i 位三进制到 j 位，且二进制数位和为 k，三进制数位和为 l，是否卡上界的方案数，但是发现这根本没有办法转移，因为进制之间的关系太复杂了，我们貌似只能考虑对其中一种数位进行 dp，三进制的位数更少，且转移二进制更为方便，我们考虑选择对三进制进行 dp。

设 f(i,j,0/1) 表示考虑完了位数大于 i 的三进制位，当前二进制数为 j，是否卡上界的方案数，最后在 i=-1 时统计答案。

但是这样跑起来比二进制还慢。但是我们注意到关于这种进制数位的题，随便优化一个个位置就是指数级别的优化。我们发现对于 f(i,j,0/1)，不考虑进位的话只会对后 \lceil(i+1)\log_23\rceil 个数位产生影响，设其为 ef(i)，因为之后最终的 j 只会在 [j,j+3^{i+1}) 中出现。总之一个思想，根据可转移的范围去优化状态，我们设 f(i,j,0/1,0/1) 表示考虑完高于 i 的进制位，当前值模 ef(i) 的值为 j，是否进位，是否顶上界的答案。

不太熟这种 trick 的人可能有点难以理解，实际上就是将原本的 f(i,j,0/1) 按 j\bmod ef(i) 划分到 ef(i) 个等价类里，它们是可以完成转移的。

转移可以根据我们钦定的进位，和加的值以及后继状态是否钦定进位去算固定的转移系数。相当于是说，首先枚举当前位是几，然后枚举后继是否进位，看加起来后看当前能否进位，也就是加起来的数是否 \ge ef(i)。可以的话，转移系数就只跟确定位置 1 的个数有关了。

但是这样没做完，我们忙活半天这个复杂度还是劣完了。我们不难感受到 i 越大三进制位的选择越少，i 越小二进制位的选择越少，而进制为的变化带来的力量是巨大的，所以考虑根号分治，让 i\ge B 的时候直接暴搜，i<B 的时候记忆化，这样复杂度就变成 \mathcal{O}(3^B+\frac{n}{3^B})，我的 B 取的 12。

这题还有一些其它做法，总之都是利用了位的贡献可拆然后去搞类似分治的东西，这是一个很好的思想。

代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i (l); i <= (r); ++ i)
#define rrp(i, l, r) for (int i (r); i >= (l); -- i)
#define eb emplace_back
using namespace std;
#define pii pair <int, int>
#define inf 1000000000ll
#define ls (p << 1)
#define rs (ls | 1)
#define fi first
#define se second
constexpr int N = 1e7 + 5, M = 60 + 5, P = 998244353;
typedef long long ll;
typedef unsigned long long ull;
inline ll rd () {
  ll x = 0, f = 1;
  char ch = getchar ();
  while (! isdigit (ch)) {
    if (ch == '-') f = -1;
    ch = getchar ();
  }
  while (isdigit (ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar ();
  }
  return x * f;
}
int qpow (int x, int y) {
  int ret (1);
  for (; y; y >>= 1, x = x * x % P) if (y & 1) ret = ret * x % P;
  return ret;
}
int t[N], * o, * f[13][2];
ll ef[M], py[M], p3[M], n, x, y, z;
ll pw[M];
int m;
int dfs (int step, ll now, bool go, bool up) {
  if (step == -1) return ! go;
  if (step <= 12 && ! up && f[step][go][now] > -1) return f[step][go][now];
  ll ret (0);
  int lim = up ? (n / p3[step] % 3) : 2;
  ll cur (1);
  rep (i, 0, lim) {
    if (i > 0) cur = cur * pw[step] % P * z % P;
    ll tmp (now + p3[step] * i);
    rep (j, 0, 1) {
      ll val (step ? ef[step - 1] : 1);
      ll nxt (tmp + j * val);
      if ((nxt >= ef[step]) == go) {
        nxt -= ef[step] * go;
        ret += py[__builtin_popcountll (nxt / val)] * cur % P * dfs (step - 1, nxt % val, j, up & (i == lim));
      }
    }
  }
  ret %= P;
  if (step <= 12 && ! up) f[step][go][now] = ret;
  return ret;
}
int32_t main () {
  n = rd (), x = rd (), y = rd (), z = rd ();
  p3[0] = 1, py[0] = 1;
  ll c (1);
  while (c <= n) c *= 3, ++ m;
  pw[0] = x;
  rep (i, 1, m) p3[i] = p3[i - 1] * 3, pw[i] = pw[i - 1] * pw[i - 1] % P * pw[i - 1] % P;
  rep (i, 1, M - 1) py[i] = py[i - 1] * y % P;
  o = t;
  rep (i, 0, m) {
    ef[i] = 1ll << (int) ceil (log2 (3) * (i + 1));
    if (i <= 12) {
      f[i][0] = o, o += ef[i], f[i][1] = o, o += ef[i];
      rep (j, 0, ef[i] - 1) f[i][0][j] = f[i][1][j] = -1;
    }
  }
  cout << (dfs (m, 0, 0, 1) - 1 + P) % P;
}