链接：
题解：
一种暴力的想法是容斥，那么答案为
∑
S
(
−
1
)
∣
S
∣
(
n
−
∑
j
∈
S
(
b
j
−
c
+
1
)
+
m
−
1
m
)
\sum_{S} (-1)^{|S|}\binom{n-\sum_{j\in S}(b^j-c+1)+m-1}{m}
S
∑
(
−
1
)
∣
S
∣
(
m
n
−
∑
j
∈
S
(
b
j
−
c
+
1
)
+
m
−
1
)
令
f
(
x
)
=
(
x
k
)
f(x) = \binom{x}{k}
f
(
x
)
=
(
k
x
)
将它变成
k
k
k
次多项式，那么由斯特林数容斥得
f
(
x
)
=
∑
i
=
0
k
(
−
1
)
k
−
i
[
k
i
]
x
i
k
!
f(x) = \frac{\sum_{i=0}^k (-1)^{k-i}{k\brack i} x^i}{k!}
f
(
x
)
=
k
!
∑
i
=
0
k
(
−
1
)
k
−
i
[
i
k
]
x
i
c
c
c
的限制不太好算，直接暴力枚举
∣
S
∣
|S|
∣
S
∣
就可以去掉
c
c
c
的贡献了，那么只需要对于每个
i
i
i
算
(
∑
j
∈
S
b
j
)
i
(\sum_{j\in S}b^j)^i
(
∑
j
∈
S
b
j
)
i
。
预处理
f
(
i
,
j
,
k
)
f(i, j, k)
f
(
i
,
j
,
k
)
表示考虑
b
1
,
b
2
,
⋯
 
,
b
i
b^1, b^2, \cdots, b^i
b
1
,
b
2
,
⋯
,
b
i
，选出
j
j
j
个数和的
k
k
k
次方之和，那么由二项式定理
f
(
i
,
j
,
k
)
=
f
(
i
−
1
,
j
,
k
)
+
∑
l
=
0
k
f
(
i
−
1
,
j
−
1
,
l
)
b
i
(
k
−
l
)
(
k
l
)
f(i,j,k) = f(i-1,j,k) + \sum_{l=0}^k f(i-1,j-1,l) b^{i(k-l)} \binom{k}{l}
f
(
i
,
j
,
k
)
=
f
(
i
−
1
,
j
,
k
)
+
l
=
0
∑
k
f
(
i
−
1
,
j
−
1
,
l
)
b
i
(
k
−
l
)
(
l
k
)
接下来枚举脱离限制的最高位，之后的数可以任意选，用预处理的
f
f
f
来计算。
代码：
#include <bits/stdc++.h>
using namespace std;
const int md = 998244353;
inline void add(int &x, int y) {
x += y;
if (x >= md) {
x -= md;
}
}
inline void sub(int &x, int y) {
x -= y;
if (x < 0) {
x += md;
}
}
inline int mul(int x, int y) {
return (int) ((long long) x * y % md);
}
int main() {
#ifdef wxh010910
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, b, c;
string str;
int qq = 0;
while (cin >> n >> b >> c >> str) {
vector<vector<int>> binom(n + 1, vector<int>(n + 1));
for (int i = 0; i <= n; ++i) {
binom[i][0] = 1;
for (int j = 1; j <= i; ++j) {
binom[i][j] = binom[i - 1][j];
add(binom[i][j], binom[i - 1][j - 1]);
}
}
vector<vector<int>> stirling(n + 1, vector<int>(n + 1));
stirling[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
stirling[i][j] = stirling[i - 1][j - 1];
add(stirling[i][j], mul(stirling[i - 1][j], i - 1));
}
}
vector<int> inv_fact(n + 1);
inv_fact[0] = inv_fact[1] = 1;
for (int i = 2; i <= n; ++i) {
inv_fact[i] = mul(md - md / i, inv_fact[md % i]);
}
for (int i = 2; i <= n; ++i) {
inv_fact[i] = mul(inv_fact[i], inv_fact[i - 1]);
}
vector<int> digits(str.size());
for (int i = 0; i < (int) str.size(); ++i) {
digits[i] = str[i] - '0';
}
reverse(digits.begin(), digits.end());
vector<int> mod_digits;
while (!digits.empty()) {
long long remainder = 0;
for (int i = (int) digits.size() - 1; ~i; --i) {
remainder = remainder * 10 + digits[i];
digits[i] = remainder / b;
remainder %= b;
}
while (!digits.empty() && !digits.back()) {
digits.pop_back();
}
mod_digits.push_back(remainder);
}
int value = 0;
for (int i = mod_digits.size() - 1; ~i; --i) {
value = mul(value, b);
add(value, mod_digits[i]);
}
add(value, n - 1);
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
dp[0][0][0] = 1;
for (int i = 1, w = b; i <= n; ++i, w = mul(w, b)) {
vector<int> power(n + 1);
power[0] = 1;
for (int i = 0; i < n; ++i) {
power[i + 1] = mul(power[i], w);
}
dp[i] = dp[i - 1];
for (int j = 1; j <= i; ++j) {
for (int k = 0; k <= n; ++k) {
for (int l = 0; l <= k; ++l) {
add(dp[i][j][k], mul(mul(binom[k][l], power[k - l]), dp[i - 1][j - 1][l]));
}
}
}
}
int ans = 0;
for (int take = 0; take <= n; ++take) {
vector<int> power_value(n + 1);
power_value[0] = 1;
for (int i = 0; i < n; ++i) {
power_value[i + 1] = mul(power_value[i], value);
}
vector<int> power_b(mod_digits.size());
power_b[0] = 1;
for (int i = 1; i < (int) mod_digits.size(); ++i) {
power_b[i] = mul(power_b[i - 1], b);
}
vector<int> coef(n + 1);
for (int i = 0; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
int ways = mul(stirling[n][j], mul(binom[j][i], mul(power_value[j - i], inv_fact[n])));
if ((i + j + n + take) % 2 == 1) {
sub(coef[i], ways);
} else {
add(coef[i], ways);
}
}
}
int sum = 0;
int cnt = 0;
for (int i = (int) mod_digits.size() - 1; ~i; --i) {
if (mod_digits[i]) {
int lim = min(n, max(i - 1, 0));
vector<int> power_sum(n + 1);
power_sum[0] = 1;
for (int j = 0; j < n; ++j) {
power_sum[j + 1] = mul(power_sum[j], sum);
}
for (int j = 0; j <= n; ++j) {
int ways = 0;
for (int k = 0; k <= j; ++k) {
add(ways, mul(binom[j][k], mul(dp[lim][take - cnt][k], power_sum[j - k])));
}
add(ans, mul(ways, coef[j]));
}
if (cnt < take && i <= n && i) {
add(sum, power_b[i]);
++cnt;
if (mod_digits[i] > 1) {
power_sum[0] = 1;
for (int j = 0; j < n; ++j) {
power_sum[j + 1] = mul(power_sum[j], sum);
}
for (int j = 0; j <= n; ++j) {
int ways = 0;
for (int k = 0; k <= j; ++k) {
add(ways, mul(binom[j][k], mul(dp[lim][take - cnt][k], power_sum[j - k])));
}
add(ans, mul(ways, coef[j]));
}
break;
}
} else {
break;
}
}
}
mod_digits[0] += c - 1;
if (c > 1) {
for (int i = 0; i + 1 < (int) mod_digits.size(); ++i) {
if (mod_digits[i] >= b) {
mod_digits[i] -= b;
mod_digits[i + 1]++;
}
}
if (mod_digits.back() >= b) {
mod_digits.back() -= b;
mod_digits.push_back(1);
}
} else {
for (int i = 0; i + 1 < (int) mod_digits.size(); ++i) {
if (mod_digits[i] < 0) {
mod_digits[i] += b;
mod_digits[i + 1]--;
}
}
if (mod_digits.back() < 0) {
break;
}
}
value = ((value + c - 1) % md + md) % md;
}
cout << "Case #" << ++qq << ": " << ans << "\n";
}
return 0;
}