luogu#P8962. 「WHOI-4」yadiw. Slua, gassp, lhtubs.

「WHOI-4」yadiw. Slua, gassp, lhtubs.

题目背景

If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

题目描述

小 F 有一个奇妙的数组 aaaa 中没有重复的元素,长度为 nn,他使用std::sort将他排序了,认为它是有序的,所以他正在使用这样的方法进行二分查找。显然,能否查到只和数列的离散化结果有关,所以你可以直接把 aa 看作 1n1\sim n 的一个排列。

int search(int key) {
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] < key)
      l = mid + 1;
    else if (a[mid] == key)
      return mid;
    else
      r = mid - 1;
  }
  return -1;
}

不幸的是,小 W 为了让他戒掉万能头,在bits/stdc++.h中写了#define sort random_shuffle,这意味着 aa 实际是一个随机的排列。

现在,对于所有在 11NN 范围内的 nn,以及所有在 11nn 范围内的 kk,在 aa 数列的所有排列中,有几个可以正确地找到第 kk 小的元素 keykey(即返回值非 1-1)?由于答案可能过大,请输出它对给定模数 pp 取模的结果。

输入格式

一行两个正整数 p,Np,N

输出格式

NN 行,第 nnnn 个正整数,代表在 nn 个元素中找 kk 能找到的方案数。

998244353 5

1
1 2
4 4 4
12 12 14 18
48 54 60 66 72

提示

数据范围

本题采用 Subtask 评测。

  • Subtask 1(1010 pts):N=10N=10p998244352 p\ge998244352
  • Subtask 2(2525 pts):N=100N=100p1009p\ge1009 且为素数
  • Subtask 3(2525 pts):N=400N=400p1009p\ge1009 且为素数
  • Subtask 4(4040 pts):N=400N=400

对于所有数据,10N40010\le N\le 4002p998244353 2\le p\le998244353