A – Count

真难。

简单来讲，题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\)，然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)（注意，\(A\)并没有被整体取模，只是各项余数之和），可知\(A \mod m = n \mod m\)，且\(A\)的上限就是\(A = k(m – 1)\)（各项上限）。

我们做了这样一个设置之后，问题就可以转换为：对于每一个不同的\(A\)，满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先，我们可以先枚举每一个\(A\)来缩小问题的范围，根据\(A\)所满足的条件，可以这样遍历\(i\)来获得每一个\(A\)：

\[ A = im + (n \mod m), i \in [0, \lfloor \frac{k(m – 1) – (n \mod m)}{m} \rfloor ] \]

我们获得\(A\)的复杂度其实就是\(O(k)\)级别的。现在，我们针对每一个\(A\)来进行计数，计算有多少个这样\(k\)元组。首先，需要知道：

对于一个不定方程\(\sum_{i = 1}^n x_i = B\)，正整数解为\({B – 1 \choose n – 1}\)（基于插板法）。

这个很重要，之后的解释中都会用到这个结论。在\(A\)中，很有可能会出现大于\(m\)的元素\(x_i\)，我们可以枚举有多少个这样大于\(m\)的元素进行计算。很可惜的是，我们只能计算至少有\(i\)个大于\(m\)的元素的方案数，并不能计算恰好为零的答案，好在利用这个我们还是可以进行容斥的，所以计算答案的式子：

\[ \sum_{A = im + n \mod m} {k + \lfloor \frac{n – A}{m} \rfloor – 1 \choose k – 1} \sum_{j = 0}^{min(k, \lfloor \frac{A}{m – 1} \rfloor)} (-1)^j {A – j(m – 1) – 1 \choose k – 1} {k \choose j} \]

注释：

• \({A – j(m – 1) – 1 \choose k – 1}\)的意思就是从已经扣除掉了至少\(j\)个\((m – 1)\)之后再次求解不定方程的个。
• \({k \choose j}\)是那些大于\(m\)元素集合的选法。
• \({k + \lfloor \frac{n – A}{m} \rfloor – 1 \choose k – 1}\)是从剩下多余的\(m\)中挑选出一些放入那些元素的放法。

这道题的题解写的不是很详细，也没有人写过这题的题解，所理解这个东西十分费劲。如果有任何疑问，请留言，我会尽快处理。

// A.cpp
// More comments on this problem at https://kalorona.com
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 998244353, MAX_N = 1e7 + 10;

ll n, m, k, inv[MAX_N];
int fac[MAX_N], fac_inv[MAX_N];

ll comb(ll n_, ll k_)
{
    if (n_ < k_)
        return 0;
    if (n_ < MAX_N && k_ < MAX_N)
        return 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod;
    ll ans = 1;
    for (ll i = 1; i <= k_; i++)
        ans = 1LL * ans * inv[i] % mod * ((n_ - k_ + i) % mod) % mod;
    return ans;
}

int main()
{
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &m, &k);
    inv[1] = 1;
    for (ll i = 2; i < MAX_N; i++)
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = fac_inv[0] = 1;
    for (int i = 1; i < MAX_N; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod, fac_inv[i] = 1LL * fac_inv[i - 1] * inv[i] % mod;
    ll ans = 0;
    for (ll A = n % m; A <= 1LL * k * (m - 1); A += m)
    {
        ll opt = 1, res = 0;
        for (ll i = 0; i <= k && 1LL * i * (m - 1) <= A; i++)
        {
            res = (res + opt * comb(A - i * (m - 1) - 1, k - 1) % mod * comb(k, i) % mod + mod) % mod;
            opt = -opt;
        }
        ans = (ans + res * comb(k + (n - A) / m - 1, k - 1) % mod + mod) % mod;
    }
    printf("%lld", ans);
    return 0;
}