{"problem":{"name":"[PA 2024] Grupa permutacji","description":{"content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 2 [Grupa permutacji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/gru/)** 在本题中，我们将处理 $n$ 个元素的排列。$n$ 个元素的排列是由 $1$ 到 $n$（包含两端）的 $n$ 个","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":15000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10353"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 2 [Grupa permutacji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/gru/)**\n\n在本题中，我们将处理 $n$ 个元素的排列。$n$ 个元素的排列是由 $1$ 到 $n$（包含两端）的 $n$ 个不同的自然数组成的序列。将排列 $a_1,a_2,\\ldots,a_n$ 和排列 $b_1,b_2,\\ldots,b_n$ 复合起来，会得到排列 $a_{b_1},a_{b_2},\\ldots,a_{b_n}$。我们称任意满足 $i<j$ 且 $p_i>p_j$ 的数对 $(i,j)$ 为排列 $p_1,p_2,\\ldots,p_n$ 的逆序对。\n\nBytie 是 $n$ 个元素的排列的忠实粉丝。他非常喜欢它们，并且其中有一些是他最喜欢的。他决定开始在一张纸上写下通过复合他最喜欢的排列（以任何顺序，也许多次使用其中一些排列）能得到的所有排列，并小心翼翼地保证不写出任何排列超过一次。\n\n毫无疑问，他很快就用完了纸张。然后 Bytie 有一个问题：如果他列出所有可能的排列，它们平均会有多少个逆序对？\n\n帮他写一个程序来计算这个值。更具体地说，输出答案对 $10^9+7$ 取模后的值（详见「输出格式」部分）。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $k\\ (1\\le n,k\\le 3\\,000)$，分别表示排列的长度和 Bytie 最喜欢的排列个数。\n\n接下来 $k$ 行，第 $i$ 行包含 $n$ 个互不相同的整数 $a_{i,1},a_{i,2},\\ldots,a_{i,n}\\ (1\\le a_{i,j}\\le n)$，表示 Bytie 第 $i$ 个最喜欢的排列。\n\n## Output\n\n输出一行一个整数，表示 Bytie 可能写下的所有排列中逆序对数的平均值模 $10^9+7$ 后的结果。\n\n形式化地说，令结果为 $\\frac{p}{q}$，其中 $q\\neq 0$ 且 $\\gcd(p,q)=1$。则输出 $p\\cdot q^{-1}\\pmod{10^9+7}$，其中 $q^{-1}$ 表示在 $1,2,\\ldots,10^9+6$ 中唯一满足 $q\\cdot q^{-1}\\equiv 1\\pmod{10^9+7}$ 的整数。\n\n可以证明，对于所有满足条件的测试数据，其结果是一个有理数，其不可约形式的分母不能被 $10^9+7$ 整除。\n\n[samples]\n\n## Background\n\nPA 2024 2A\n\n## Note\n\n在第一组样例中，Bytie 会写下排列 $\\{1,2,3\\}$（有 $0$ 个逆序对），排列 $\\{2,3,1\\}$（有 $2$ 个逆序对）和排列 $\\{3,1,2\\}$（有 $2$ 个逆序对）。因此平均逆序对个数为 $\\frac{4}{3}$。且 $3^{-1}\\equiv 333333336\\pmod{10^9+7}$，因此答案为 $333333336\\cdot 4\\equiv 1333333344\\equiv 333333337\\pmod{10^9+7}$。\n\n在第二组样例中，Bytie 会写下 $5$ 个元素的所有排列。容易证明它们平均有 $5$ 个逆序对。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10353","tags":["2024","群论","置换","期望","随机化","PA（波兰）"],"sample_group":[["3 1\n2 3 1\n","333333337\n"],["5 2\n2 1 3 4 5\n2 3 4 5 1\n","5"]],"created_at":"2026-03-03 11:09:25"}}