I. 出给 paul-lu 的数数题

Codeforces

IDCF10217I

Time10000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

中国科学院大学的著名 JB 选手 bibibibi，想当年还在北理工打算法竞赛时候就是一个全能王，所有的算法题目里就没有他不能嘴巴 AC 的。这天他听说 Paul（lu）Lu（pao）学长挺会数数的，于是决定出一道数数的题目来考一考他：已知在一个 $n times n$ 的棋盘里，每个格子都可以填上一个范围为 $[ 1, k ]$ 的正整数。定义棋盘中的某个格点是 _bi点_ 当且仅当满足：设 $B_i$ 为棋盘中恰好 $i$ 个 _bi点_ 的方案数，请你计算 $sum limits_{i = 0}^(n^2) (i^2 dot.op B_i)$，答案可能很大，请取模 $10^9 + 7$。第一行输入一个正整数 $T " "(1 <= T <= 20)$，表示数据组数。接下来 $T$ 组数据，每组数据输入两个正整数 $n$ 和 $k " "(1 <= n, k <= 200)$，由空格间隔开，分别表示棋盘的大小和每个格点内可填数的范围上限。对于每组数据，请输出一行，表示计算结果取模 $10^9 + 7$ 的答案，注意换行。 ## Input 第一行输入一个正整数 $T " "(1 <= T <= 20)$，表示数据组数。接下来 $T$ 组数据，每组数据输入两个正整数 $n$ 和 $k " "(1 <= n, k <= 200)$，由空格间隔开，分别表示棋盘的大小和每个格点内可填数的范围上限。 ## Output 对于每组数据，请输出一行，表示计算结果取模 $10^9 + 7$ 的答案，注意换行。 [samples]

**Definitions** Let $ n, k \in \mathbb{Z}^+ $. Consider an $ n \times n $ grid where each cell is assigned a value in $ [1, k] $. A cell is a *bi-point* if it is the unique maximum in its row and column. Let $ B_i $ be the number of grid assignments with exactly $ i $ bi-points. **Constraints** 1. $ 1 \leq T \leq 20 $ 2. For each test case: $ 1 \leq n, k \leq 200 $ **Objective** Compute: $$ \sum_{i=0}^{n^2} i^2 \cdot B_i \mod (10^9 + 7) $$

API Response (JSON)

{
  "problem": {
    "name": "I. 出给 paul-lu 的数数题",
    "description": {
      "content": "中国科学院大学的著名 JB 选手 bibibibi，想当年还在北理工打算法竞赛时候就是一个全能王，所有的算法题目里就没有他不能嘴巴 AC 的。这天他听说 Paul（lu）Lu（pao）学长挺会数数的，于是决定出一道数数的题目来考一考他： 已知在一个 $n times n$ 的棋盘里，每个格子都可以填上一个范围为 $[ 1, k ]$ 的正整数。定义棋盘中的某个格点是 _bi点_ 当且仅当满足： ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10217I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "中国科学院大学的著名 JB 选手 bibibibi，想当年还在北理工打算法竞赛时候就是一个全能王，所有的算法题目里就没有他不能嘴巴 AC 的。这天他听说 Paul（lu）Lu（pao）学长挺会数数的，于是决定出一道数数的题目来考一考他：\n\n已知在一个 $n times n$ 的棋盘里，每个格子都可以填上一个范围为 $[ 1, k ]$ 的正整数。定义棋盘中的某个格点是 _bi点_ 当且仅当满足：\n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $. Consider an $ n \\times n $ grid where each cell is assigned a value in $ [1, k] $. A cell is a *bi-point* if it is the unique maximum in its row and co...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments