UOJ Logo

NOI.AC

3S 512MB

#239. count

统计

【题目描述】

给定两个整数 $n$,$m$, 求 k 元组 ($a_1,a_2,\dots,a_k$) 的个数,满足 $a_1,a_2,\dots,a_k$ 为正整数,$\sum^{k}_{i=1} a_i = n$且$a_1,a_2,\dots,a_k$均不是m的倍数。

【输入格式】

共一行,三个正整数 $n,m,k$。

【输出格式】

共一行,为 $k$ 元组的个数,答案对 $998244353$ 取模

【样例 1 输入】

5 3 3

【样例 1 输出】

3

【数据范围】

对于 $30%$ 的数据,$n \leq 2000 ,k \leq 3$

对于 $50%$ 的数据,$n \leq 10^{18},m \leq 2000,k \leq 3 $

对于 $70%$ 的数据,$n \leq 10^{18},m \leq 5000,k \leq 20 $

对于 $100%$ 的数据,$n \leq 10^{18} ,m \leq 5000,k \leq 2000$