Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
Statistics

1 测测你的FFT(fft)

1.1 题目描述

给定 $n, m, k$,考虑所有长为 $n$ 的 01 串,满足任意连续 $m$ 个字符都有至少 $k$ 个 1。

定义一个串的权值为这个串中 $1$ 的个数,记 $X$ 为所有满足条件的串中权值最小的权值,

求有多少满足条件的串权值等于 $X$。

1.2 输入格式

第一行一个数 $T$,表示数据组数。

对于每组数据,一行三个数 $n, m, k$。

1.3 输出格式

T 行每行一个非负整数,表示串的个数 $\text{mod} 998244353$ 的结果。

1.4 样例输入

4
2 2 1
4 2 1
50 10 3
100000000 1000000 100000

1.5 样例输出

2
3
16195608
222752520

1.6 样例解释

第一组数据,满足条件的串有 $01,10,11$。 其中 $01,10$ 的权值为 $1$,$11$ 的权值为 $2$。 因此最小值是 $1$,个数是 $2$,只需输出 $2$。