mx的组合数 - 题目 - Universal Online Judge

给定 $p, n, l, r$ ，其中 $p$ 是质数。请对 $0$ 到 $p - 1$ 的所有值 $a$ ，输出满足 $l \leq x \leq r$ 且 $(\binom{x}{n}) \equiv a (\mod p)$ 的 $x$ 的个数对 $998244353$ （ $7 \times 17 \times 2^{23} + 1$ ，一个质数）取模后的结果。其中 $(\binom{x}{n})$ 是二项式系数，即 $x$ 个数里选 $n$ 个的方案数。

输入格式

一行四个非负整数，分别表示 $p, n, l, r$ ，保证 $l \leq r$ 。

输出格式

$p$ 行，第 $i$ 行表示 $a = i - 1$ 时的答案。

样例一

input

7 3 1 7

output

explanation

$(\binom{1}{3}) = (\binom{2}{3}) = 0 \equiv 0 (\mod 7)$

$(\binom{3}{3}) = 1 \equiv 1 (\mod 7)$

$(\binom{4}{3}) = 4 \equiv 4 (\mod 7)$

$(\binom{5}{3}) = 10 \equiv 3 (\mod 7)$

$(\binom{6}{3}) = 20 \equiv 6 (\mod 7)$

$(\binom{7}{3}) = 35 \equiv 0 (\mod 7)$

故模 $7$ 意义下值为 $0$ 的有三个，值为 $1, 3, 4, 6$ 的各一个，因此样例输出即为所求答案。

限制与约定

对于 10% 的数据， $n, l, r \leq 1000$ 。

对于 20% 的数据， $n, l, r \leq 100000$ 。

对于另外 20% 的数据， $r - l \leq 10000$ 。

对于另外 30% 的数据， $p \leq 1000$ ，且某些数据点中 $p \leq 100$ 。

对于 100% 的数据， $p \leq 30000$ ， $l, r, n \leq 10^{30}$ 。

此外为了照顾被卡常数的同学，本题存在过渡数据。为了照顾不知道高精度的小朋友，在各种类型的数据中均分布有一些 $l, r, n \leq 10^{18}$ 的数据。

时间限制： $2 s$

空间限制： $256 MB$

来源

matthew99

题解

https://matthew99.blog.uoj.ac/blog/240

下载

样例数据下载

Universal Online Judge

UOJ

#86. mx的组合数