UOJ Logo Universal Online Judge

UOJ

#86. mx的组合数

统计

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

输入格式

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

输出格式

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

样例一

input

7 3 1 7

output

3
1
0
1
1
0
1

explanation

${1 \choose 3} = {2 \choose 3} = 0 \equiv 0 \pmod{7}$

${3 \choose 3} = 1 \equiv 1 \pmod{7}$

${4 \choose 3} = 4 \equiv 4 \pmod{7}$

${5 \choose 3} = 10 \equiv 3 \pmod{7}$

${6 \choose 3} = 20 \equiv 6 \pmod{7}$

${7 \choose 3} = 35 \equiv 0 \pmod{7}$

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

限制与约定

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

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

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

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

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

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

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

来源

matthew99

题解

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

下载

样例数据下载