只会处理 $y = 1$ 的情况。唉。
设 $f_{i, j, k}$ 表示当前填到从高到低第 $i$ 位,是否顶上界情况为 $j$,数位和为 $k$ 时前面 $x$ 的次幂和是多少。暴力转移复杂度为 $O((\log_3 n) ^ 2)$。期望得分 $35$。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#define int long long
#define vit vector<int>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
using namespace std;
const int N = 1e7 + 10;
const int mod = 998244353;
int px[N], py[150], pz[150], a[N], b[N];
int n, x, y, z, ans, f[150][2][150];
int cnt = 0, bit[150], pw[150][3];
void sub() {
while (n) bit[ ++ cnt] = n % 3ll, n /= 3ll;
rep(i, 0, 2) pw[0][i] = (i == 0 ? 1 : (i == 1 ? x : x * x % mod));
rep(i, 1, cnt) rep(j, 0, 2)
pw[i][j] = pw[i - 1][j] * pw[i - 1][j] % mod * pw[i - 1][j] % mod;
rep(i, 0, bit[cnt]) f[cnt][i == bit[cnt]][i] = pw[cnt - 1][i];
dep(i, cnt, 2) rep(j, 0, 2) rep(k, 0, 1) rep(l, 0, 100) {
if (k and j > bit[i - 1]) continue;
(f[i - 1][k & (j == bit[i - 1])][l + j] += f[i][k][l] * pw[i - 2][j] % mod) %= mod;
} pz[0] = 1; rep(i, 1, 100) pz[i] = pz[i - 1] * z % mod;
rep(i, 0, 100) (ans += (f[1][0][i] + f[1][1][i]) * pz[i] % mod) %= mod;
printf("%lld\n", ans - 1); return;
}
signed main() {
scanf("%lld%lld%lld%lld", &n, &x, &y, &z);
if (y == 1) { sub(); return 0; }
px[0] = py[0] = pz[0] = 1;
rep(i, 1, n) px[i] = px[i - 1] * x % mod;
rep(i, 1, 50) py[i] = py[i - 1] * y % mod;
rep(i, 1, 50) pz[i] = pz[i - 1] * z % mod;
rep(i, 1, n) a[i] = a[i >> 1] + (i & 1);
rep(i, 1, n) b[i] = b[i / 3] + (i % 3);
rep(i, 1, n) (ans += px[i] * py[a[i]] % mod * pz[b[i]] % mod) %= mod;
cout << ans << endl; return 0;
}
大佬爆切黑题,然后来 AcWing 嘲讽我这个菜弱awa……
不是我只会写 35 分部分分。。。