#2423. 排列
排列
排列
题目描述
NOI 2022 安徽省省队选拔 排列(perm) 排列(perm) 【题目描述】 对于一个长度为n 的排列P = (p1, p2, . . . , pn) 和整数k ≥0,定义P 的k 次幂 P (k) = ( p(k) 1 , p(k) 2 , . . . , p(k) n ) , 该排列的第i 项为 p(k) i
i, k = 0, p(k−1) pi , k > 0. 容易证明任意排列的任意次幂都是一个排列。 定义排列P 的.循.环.值v(P) 为最小的.正.整.数k 使得P (k+1) = P。 给出一个长度为n 的排列A = (a1, a2, . . . , an),对于整数1 ≤i, j ≤n,定义f(i, j): 若存在k ≥0 使得a(k) i = j,则f(i, j) = 0,否则设排列Aij 为将排列A 的第i 项ai 和 第j 项aj 交换后得到的排列,则f(i, j) = v(Aij)。 求∑n i=1 ∑n j=1 f(i, j) 的值。答案可能很大,你只需要输出其对(109 + 7) 取模的结 果。 【输入格式】 从文件perm.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入数据的第一行为一个整数T,表示测试数据组数。 对于每组测试数据,第一行一个正整数n 表示排列的长度,接下来一行n 个整数 a1, a2, . . . , an,描述输入的排列。 【输出格式】 输出到文件perm.out 中。 对于每组数据输出一行一个整数,表示题目所求的答案对(109 + 7) 取模的结果。 【样例1 输入】 1 2 2 3 3 1 2 3 4 3 5 2 3 1 第2 页 共15 页
NOI 2022 安徽省省队选拔 排列(perm) 【样例1 输出】 1 12 2 0 【样例1 解释】 对于第一组测试数据,f(1, 2) = f(2, 1) = f(2, 3) = f(3, 2) = f(1, 3) = f(3, 1) = 2, 其余的f(i, j) 均为0。 对于第二组测试数据,所有的f(i, j) 均为0。 【样例2】 见选手目录下的perm/perm2.in 与perm/perm2.ans。 该组样例中,第一个测试数据满足n ≤35,前四个测试数据满足n ≤200,所有测 试数据满足n ≤2500。 【样例3】 见选手目录下的perm/perm3.in 与perm/perm3.ans。 该组样例中,第一个测试数据满足特殊性质A,第二个测试数据满足特殊性质B, 第三个测试数据满足特殊性质C,前四个测试数据满足n ≤105,第五个测试数据满足 n ≤5 × 105。 特殊性质的具体内容参见子任务部分。 【子任务】 对于100% 的测试数据,1 ≤T ≤5,1 ≤n ≤5 × 105,1 ≤ai ≤n。 测试点编号 n ≤ 特殊性质 1 ∼2 105 A 3 35 无 4 200 5 2500 6 105 B 7 C 8 无 9 ∼10 5 × 105 第3 页 共15 页
NOI 2022 安徽省省队选拔 排列(perm) 特殊性质A:ai = (i mod n) + 1。 特殊性质B:对于任意1 ≤i ≤n,存在1 ≤k ≤20,a(k) i = i。 特殊性质C:存在大小不超过10 的集合S,使得对于任意1 ≤i ≤n,存在 x ∈S, k ≥0,a(k) x = i。 【提示】 输入数据规模较大,请使用较为快速的输入方式。 第4 页 共15 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
3
1 2 3
3
2 3 1
12
0
样例 2
5
35
11 9 35 15 17 14 34 20 8 31 25 32 13 1 6 26 33 27 18 19 7 2 12 23 10 5 28 16 24 30 21 3 22 4 29
36
21 13 20 15 9 25 11 10 31 16 26 8 2 36 30 4 35 29 18 14 23 27 34 6 33 32 17 5 12 7 28 19 24 1 22 3
200
113 85 90 185 161 120 22 13 115 182 1 36 150 23 179 64 102 194 15 156 69 94 11 122 125 111 43 83 170 103 89 79 48 17 84 114 20 135 63 87 24 148 189 73 186 152 39 54 198 108 144 16 165 164 51 141 138 140 128 193 77 52 136 45 104 68 88 10 109 130 107 197 167 31 199 28 21 117 187 129 38 3 143 61 76 65 32 105 86 173 191 196 97 183 80 82 19 181 188 6 171 12 133 177 149 93 145 55 4 176 175 34 35 146 112 2 106 66 91 44 118 99 192 18 154 81 174 132 147 126 59 29 42 50 200 159 7 58 134 8 155 158 169 139 60 151 37 25 33 53 49 62 56 153 47 110 41 100 46 142 67 180 70 40 190 119 101 74 172 123 184 98 168 127 121 166 162 160 96 116 178 57 157 195 124 9 95 14 72 75 26 78 137 131 92 71 163 27 5 30
195
136 24 156 2 169 90 49 87 158 80 32 131 108 117 164 192 1 98 35 122 186 26 91 63 161 34 123 162 193 176 109 191 51 157 76 44 12 45 69 175 97 16 5 71 167 140 85 111 163 183 194 101 174 171 195 115 21 64 139 144 83 3 73 40 86 15 180 65 74 172 185 132 68 155 96 114 120 41 67 135 119 59 102 100 187 7 93 121 116 23 92 146 36 190 110 62 145 48 75 53 182 17 134 8 104 88 188 81 46 141 94 170 27 6 173 82 154 150 25 55 9 50 148 60 43 95 147 84 29 18 106 20 13 42 179 165 56 112 151 142 184 113 37 10 19 79 105 107 72 11 129 177 77 33 125 153 149 189 143 152 39 128 4 118 160 89 14 166 133 137 168 78 70 103 28 54 124 22 178 181 138 57 61 38 130 126 127 99 66 47 159 58 30 52 31
2426
2410 589 44 475 1068 1282 2314 1336 1576 1194 1307 1015 1466 63 1546 369 1155 2200 1064 903 1393 2404 1636 1311 2331 1296 61 519 1321 178 2158 1897 1034 2145 691 656 964 814 1859 1818 1553 832 1199 2050 2201 1653 1051 165 98 1008 115 588 1860 474 839 2309 2025 690 855 1016 1349 413 2330 633 2297 175 1769 1163 1842 1767 54 1761 1188 875 1305 1382 31 78 102 1483 43 77 8 2099 1768 1256 991 1096 1431 2233 203 893 2302 2363 246 352 1848 2383 1949 1857 410 1025 775 1325 495 619 2014 1297 1243 1127 1784 500 1141 699 2157 1031 765 2133 236 340 2190 1516 118 1345 681 1782 52 2074 2084 111 297 651 29 1982 1644 1002 1058 2061 1295 234 1583 2175 244 1224 249 1723 846 1139 1847 1082 553 209 1195 827 404 2236 2031 702 2108 2421 1442 2057 1972 771 1718 417 840 1479 239 1698 1684 2116 992 1420 1035 1549 1095 1218 391 299 315 1042 2038 687 899 1874 856 1142 2327 1615 2187 1037 1929 2360 229 1065 451 2091 677 891 685 918 157 645 1380 309 1966 1572 2056 221 982 1337 805 478 120 1884 415 680 227 184 797 980 1625 2337 272 1748 1696 1946 491 822 107 2012 767 2270 2277 1014 1493 1444 2161 996 820 1173 912 2228 1462 137 1603 706 1850 437 1990 2400 1586 1118 483 1275 2399 212 1729 2060 976 966 2022 1907 1759 1330 933 329 1059 494 2398 447 849 1347 1370 2373 225 2034 1754 2028 1849 308 1395 386 751 2322 2181 1129 1371 241 487 1146 1092 1389 641 1344 1659 643 1900 1048 2082 1492 2219 1228 1904 974 1070 1721 1573 595 824 2389 1798 1943 321 907 119 931 941 1041 1132 1430 1694 2321 1578 975 14 1476 1494 1519 1817 2402 1135 527 1890 2375 546 489 1705 2254 22 490 128 1736 353 1251 1438 1279 881 2366 1665 177 2143 570 610 116 1169 1138 1731 2105 2318 565 2415 859 1733 89 163 1978 938 326 368 1298 994 1913 1342 1119 800 1714 1238 2264 301 2420 467 2148 154 882 263 1906 1310 1872 1515 504 1145 2166 2350 215 1185 284 2220 574 1885 872 253 1732 281 283 1504 1227 60 914 2387 2070 1601 556 312 2385 1159 1977 481 2206 919 1272 1604 662 864 1550 1424 162 1764 794 1691 23 1638 1846 376 939 1527 139 972 1804 1611 1871 2140 492 2039 1179 532 2193 1425 2005 181 898 1989 2405 809 2051 542 2042 674 1911 1176 1547 1197 469 1725 813 1304 575 1974 1948 2176 1346 766 659 733 2121 1901 1991 521 865 2224 1518 1203 883 1162 2417 1131 2066 2086 2391 211 2371 1402 531 2089 666 2260 2115 1608 292 334 365 720 358 303 2401 1452 2016 1485 276 1287 389 1552 1447 462 913 2349 471 1594 785 1724 169 762 1366 6 1893 424 2118 647 46 219 2226 2079 2246 2326 339 1609 950 552 1670 1308 640 1406 1956 1997 1529 2347 506 1730 2393 304 18 616 1400 1500 2370 834 851 660 216 1110 1236 628 197 679 218 1889 296 1211 2339 2240 213 580 2007 1778 2045 1685 1187 1882 1912 1242 260 2095 2103 703 1517 701 684 1637 2004 1560 2243 10 1433 1374 1075 946 988 1398 2010 2333 2080 2058 740 406 1471 2164 1772 1562 1749 2358 742 1215 2030 1367 774 1214 1775 1109 897 17 2255 66 568 1047 19 2077 1716 550 1839 1524 2211 1639 1448 2348 1567 2221 926 15 843 1334 1935 1108 1994 829 1522 710 1357 1571 2109 2281 336 2114 251 126 71 2384 1825 1757 1538 854 1200 67 2403 1154 1081 1117 625 736 1568 1019 973 783 692 2081 357 1992 2136 989 1362 64 693 592 385 727 2097 1115 1955 1324 1917 925 1934 152 293 1459 1629 195 1481 53 185 948 2229 607 2273 436 325 484 347 983 796 1017 95 788 113 206 773 194 30 1499 1088 1674 700 2153 909 557 725 2065 749 911 1193 1643 1439 738 841 2075 91 1936 1999 138 479 1171 1870 262 1157 867 1666 830 1183 348 145 927 1511 191 1407 275 1654 1921 1399 2131 1717 962 1361 1719 70 1823 1920 2311 2107 1993 2300 401 998 2214 717 1923 916 1783 1863 1269 395 1428 176 1066 1067 648 1450 637 959 306 166 1742 744 623 180 1681 446 1102 1000 880 1816 2257 1965 1582 1646 1555 1006 1384 993 298 1001 1026 2368 650 1329 2188 1838 2015 537 448 1976 2068 450 1565 1359 657 2026 1240 562 1679 205 231 686 408 1084 1036 711 591 130 858 2316 561 142 7 2196 1727 1284 1627 1004 1273 2369 2258 1502 811 1184 164 1675 1489 922 901 764 1593 1473 548 1559 1987 148 324 1276 835 1134 1692 199 1855 569 1606 1539 2223 921 1086 1533 1044 1878 756 86 463 1204 1300 904 590 1391 1130 2259 2315 1498 669 2170 68 524 2412 2306 583 2285 1468 445 514 1737 372 1039 39 1285 2343 103 1143 541 985 2137 1683 268 1148 83 1181 1651 1854 2265 1697 1189 245 62 719 1126 1915 1239 1939 558 1652 1410 929 81 1322 1094 158 2292 1112 1822 1490 2167 346 2122 915 1469 349 1631 513 1338 2094 772 1760 2305 845 781 1057 1958 161 1463 3 2232 1397 1610 2288 728 1657 2129 1412 1418 79 2191 267 1645 1548 910 2278 2023 563 1258 2088 2111 807 155 1419 682 45 1810 1260 987 1834 821 2072 1365 505 1283 826 332 1392 1739 678 584 2354 1781 429 2192 655 730 622 338 1641 1353 2390 2100 428 1598 1820 1293 714 1478 1252 799 2169 1244 630 2146 1383 173 530 2319 2013 1777 200 708 97 423 952 273 80 2301 1508 32 1265 335 819 1556 2049 1687 1928 850 778 1437 833 2227 327 1381 522 1801 310 860 879 673 201 416 847 2172 2332 1085 136 266 28 1869 1751 2397 1688 20 1647 652 1896 1852 1220 1474 661 746 2235 96 1953 1595 1762 1061 1007 1540 254 258 1303 961 41 2367 1558 1589 431 1830 1908 632 1526 1501 1312 2149 1147 2394 520 2406 193 1581 47 958 2336 1617 342 1596 2284 2134 248 1487 1423 290 1241 397 1107 1614 1484 878 1248 1350 1299 884 1098 341 460 1486 1340 76 599 1621 2298 230 1895 1616 1774 2124 150 1100 1488 2344 1793 624 2040 1607 105 709 51 2426 631 1121 1288 789 240 36 2247 2312 1663 1453 2263 58 5 2067 1136 1358 1612 1599 1003 1746 2020 1886 997 1177 604 435 945 1701 895 1898 1649 2268 1564 601 1600 2194 1790 75 902 1040 1832 1237 1373 2199 890 801 2159 1932 1352 999 675 1294 2334 189 790 723 1750 1021 486 1093 1156 461 1505 1585 399 539 1449 2286 1150 1969 1776 1525 942 1862 2310 459 1903 1097 2269 734 1009 502 509 132 731 1073 305 2341 1864 1780 318 2130 770 2248 313 419 235 2293 1584 182 1174 2163 1709 2303 1840 300 1988 621 1221 1620 1364 1963 629 2294 1734 1710 603 608 438 2009 1700 676 2003 1690 1951 1635 2345 1079 222 1766 917 146 1460 2271 186 1664 1789 159 886 1530 863 380 1693 2018 214 1046 311 2365 121 715 302 1888 2035 1743 1050 1566 405 2249 1926 1158 317 2112 1201 518 2132 1755 1020 1071 1851 1182 1023 1574 124 1844 1331 2244 1178 1160 1277 2335 1618 2274 366 2 2251 2245 2376 56 1133 934 220 168 1409 493 533 1206 411 510 2359 750 143 1216 540 949 217 2425 2083 1514 810 970 418 1328 602 144 1821 2195 434 482 943 2361 776 432 106 1205 208 1335 285 2276 1569 320 707 1333 99 2185 1078 535 1172 754 1983 960 1403 1741 371 1554 1744 1728 759 25 1114 359 663 804 1120 698 1753 427 232 1841 1022 1411 1788 1630 924 1720 2021 986 857 1456 2055 2378 1803 2291 1592 2036 2197 1140 1814 572 1971 396 1013 1175 1011 412 125 1063 551 1634 1984 2024 114 1363 2374 1421 1111 780 1356 1580 1658 1445 2357 42 1557 2253 816 1268 1105 1861 37 2180 414 1868 1369 1341 2216 2202 1103 1536 2198 2048 350 978 612 1941 529 654 954 1196 587 2069 2152 1426 877 1919 2212 605 1605 384 1858 2238 400 995 1415 712 1660 49 2177 932 1960 990 1959 501 363 2237 2256 748 2209 1167 2380 1927 981 238 1799 1771 2102 831 1495 1699 1270 1396 2205 140 1422 50 825 1377 672 1918 798 870 2353 1686 1968 255 1642 1249 1101 2165 1528 2324 2329 1711 1281 2355 2174 1668 792 1545 1455 228 977 1417 2242 390 1355 683 547 644 760 122 1785 2063 965 2046 2382 638 2299 1995 594 1461 1191 577 1440 151 250 555 739 516 331 1379 441 2104 1087 653 869 613 818 508 2043 1247 2047 871 2213 2413 1954 2325 1166 1756 1128 1029 704 646 1319 1828 2352 649 2340 2230 108 614 1080 1682 59 430 1680 600 908 204 1219 472 392 1765 2234 1673 282 1726 782 1708 1563 688 757 1879 1930 425 889 525 1170 1512 323 16 1261 381 2409 1372 1052 735 24 817 2379 12 188 1877 1537 2296 207 1291 1712 131 1113 1613 2141 1763 2113 1808 2215 2037 223 1624 337 503 333 2098 9 967 1024 713 724 1704 2313 172 129 1662 38 1875 1497 1153 1628 1027 2280 2184 1579 2356 1480 2179 171 2304 443 1973 1323 1795 2388 1887 861 322 1945 515 316 1800 808 611 499 1543 892 1368 936 55 1436 1354 1314 27 695 1496 1544 784 1758 670 1290 1229 2151 1257 1441 1541 1387 449 1998 387 866 2017 1055 639 1996 1267 1802 1190 1672 1413 1590 758 617 1472 626 2225 791 1313 716 697 1045 2203 2342 2008 1937 1106 1254 179 1180 1975 828 544 1925 1030 747 1648 94 426 104 1812 256 1894 1164 57 971 1656 1043 1099 1223 2338 534 2423 1292 1770 585 559 1667 1924 1950 838 743 1922 1865 1262 1010 85 72 196 1570 243 1632 1234 1168 844 409 1677 2011 1933 1735 1458 1072 1245 721 1853 123 1738 134 1264 1 288 1255 269 117 642 1401 1124 488 13 581 141 2308 2071 1827 573 935 894 1706 1091 2092 127 900 1880 2241 567 627 862 1791 373 752 1985 2162 1962 257 1231 1588 1033 374 2381 307 2396 1207 153 270 2120 1867 1843 167 1577 2033 1320 1122 1074 803 2052 1796 2178 1520 485 344 2289 1165 74 609 968 1429 1209 1301 1597 1622 280 174 2128 1326 1722 969 667 1343 560 402 1315 1702 252 2183 1952 2135 1703 1957 1669 383 351 2032 1259 1376 1408 1083 1076 1806 729 1416 354 1551 2173 1151 375 2087 579 110 2395 109 2144 1457 388 848 84 930 1451 815 963 511 271 1062 2262 1503 2222 1809 1235 777 786 497 598 190 536 1233 192 512 452 876 2290 763 1152 202 658 2295 1938 1623 2424 458 1317 360 496 906 237 745 1028 498 160 464 187 1807 433 2408 1414 596 2239 665 2156 1125 1910 1149 69 2171 1532 470 566 1979 1715 147 793 477 2182 1434 634 874 1056 2110 92 2168 737 2090 1032 1327 2138 2416 928 1053 1246 578 274 289 377 2142 920 1591 2101 2150 1633 1192 1914 1470 439 2208 93 319 1253 476 149 170 2279 1981 1883 294 35 1740 1388 852 1289 606 837 133 2059 4 1386 2419 538 2125 1090 1561 1144 65 1116 1309 1482 802 444 2287 265 620 2283 1271 330 378 247 364 1348 2377 718 1792 33 586 1947 455 2126 1212 2320 1475 2062 2096 795 1446 1786 1454 1280 2160 233 112 694 2001 1881 671 853 755 34 2407 1944 1902 1707 1942 984 1286 1899 1891 1232 1360 2372 1213 2364 2351 1713 2119 1655 2323 1986 2073 1060 1831 1404 1931 1523 407 2154 1650 593 1876 1208 1819 90 355 545 2266 517 1226 868 1602 2272 1873 382 2085 1837 1779 1575 2317 523 2392 1676 1339 468 2078 291 480 1507 422 1210 156 1186 1866 421 473 1961 420 1970 1467 888 2117 1332 345 953 1752 896 1940 2064 2053 1375 1477 261 2054 944 2000 135 806 183 955 1845 394 1427 1916 2076 88 442 1069 2362 937 1250 40 277 1510 615 1435 398 1038 1509 1306 761 664 554 779 2418 1535 582 1054 1689 100 705 2127 2204 689 279 2207 2006 2386 1385 812 1432 379 403 636 768 1833 295 956 1695 957 101 1905 1587 361 356 1773 1967 543 2027 198 466 1443 1230 1829 576 571 1542 2328 2261 2267 2250 1661 564 1198 732 224 1351 2231 507 526 82 1263 2044 1217 2275 726 1794 722 242 696 1745 362 1049 951 1225 1222 1464 635 1626 2411 1394 1787 2252 2422 940 1266 787 668 287 887 923 2106 2139 259 1506 2414 393 1964 1018 1161 842 2029 823 73 2123 1123 286 2186 1077 2282 2019 1278 1892 1316 1824 597 21 753 1104 1005 457 465 456 549 314 1534 1678 1521 1671 1747 278 2147 2093 210 2189 1815 885 979 2217 1513 769 1274 873 836 1137 2002 905 1012 264 1640 226 1491 1980 1378 11 2041 1089 1390 1805 1202 1813 328 1531 1318 1909 1405 1826 1856 370 947 367 454 1465 48 741 1835 2346 1619 2307 1302 2218 1811 1797 1836 453 528 343 618 26 440 87 2155 2210
159432
45696
270681684
645993594
302433063