{"problem":{"name":"「WHOI-4」yadiw. Slua, gassp, lhtubs.","description":{"content":"小 F 有一个奇妙的数组 $a$，$a$ 中没有重复的元素，长度为 $n$，他使用`std::sort`将他排序了，认为它是有序的，所以他正在使用这样的方法进行二分查找。显然，能否查到只和数列的离散化结果有关，所以你可以直接把 $a$ 看作 $1\\sim n$ 的一个排列。 ```cpp int search(int key) {   int l = 1, r = n;   while (l <","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1200,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8962"},"statements":[{"statement_type":"Markdown","content":"小 F 有一个奇妙的数组 $a$，$a$ 中没有重复的元素，长度为 $n$，他使用`std::sort`将他排序了，认为它是有序的，所以他正在使用这样的方法进行二分查找。显然，能否查到只和数列的离散化结果有关，所以你可以直接把 $a$ 看作 $1\\sim n$ 的一个排列。\n\n```cpp\nint search(int key) {\n  int l = 1, r = n;\n  while (l <= r) {\n    int mid = (l + r) / 2;\n    if (a[mid] < key)\n      l = mid + 1;\n    else if (a[mid] == key)\n      return mid;\n    else\n      r = mid - 1;\n  }\n  return -1;\n}\n```\n\n不幸的是，小 W 为了让他戒掉万能头，在`bits/stdc++.h`中写了`#define sort random_shuffle`，这意味着 $a$ 实际是一个随机的排列。\n\n现在，对于所有在 $1$ 到 $N$ 范围内的 $n$，以及所有在 $1$ 到 $n$ 范围内的 $k$，在 $a$ 数列的所有排列中，有几个可以正确地找到第 $k$ 小的元素 $key$（即返回值非 $-1$）？由于答案可能过大，请输出它对给定模数 $p$ 取模的结果。\n\n## Input\n\n一行两个正整数 $p,N$。\n\n## Output\n\n$N$ 行，第 $n$ 行 $n$ 个正整数，代表在 $n$ 个元素中找 $k$ 能找到的方案数。\n\n[samples]\n\n## Background\n\n> 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.\n\n## Note\n\n**数据范围**\n\n**本题采用 Subtask 评测。**\n\n- Subtask 1（$10$ pts）：$N=10$，$ p\\ge998244352$；\n- Subtask 2（$25$ pts）：$N=100$，$p\\ge1009$ **且为素数**；\n- Subtask 3（$25$ pts）：$N=400$，$p\\ge1009$ **且为素数**；\n- Subtask 4（$40$ pts）：$N=400$。\n\n对于所有数据，$10\\le N\\le 400$，$ 2\\le p\\le998244353$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8962","tags":["动态规划 DP","二分","O2优化"],"sample_group":[["998244353 5\n","1\n1 2\n4 4 4\n12 12 14 18\n48 54 60 66 72"]],"created_at":"2026-03-03 11:09:25"}}