[清华集训2017] 生成树计数

题目描述

在一个 $s$ 个点的图中，存在 $s-n$ 条边，使图中形成了 $n$ 个连通块，第 $i$ 个连通块中有 $a_i$ 个点。现在我们需要再连接 $n-1$ 条边，使该图变成一棵树。对一种连边方案，设原图中第 $i$ 个连通块连出了 $d_i$ 条边，那么这棵树 $T$ 的价值为： $$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right) $$ 你的任务是求出所有可能的生成树的价值之和，对 $998244353$ 取模。

输入输出格式

输入格式

输入的第一行包含两个整数 $n,m$，意义见题目描述。接下来一行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$ $(1\le a_i< 998244353)$。 * 你可以由 $a_i$ 计算出图的总点数 $s$，所以在输入中不再给出 $s$ 的值。

输出格式

输出包含一行一个整数，表示答案。

输入输出样例

输入样例 #1

3 1
2 3 4

输出样例 #1

输入样例 #2

233 10
604230822 258609018 347836125 103063600 545593375 983656639 636383432 149579311 37952830 782185282 792399760 556879020 19276539 821164472 992758005 635410231 174811932 967712405 76287574 877354238 403371989 131233662 90928781 909518950 816498283 460305280 688669184 272529638 706529895 931734844 376928193 161521421 41104566 573769373 264585020 586697940 408186715 749973507 585282307 446139544 533914437 228442770 4774211 553190975 51362889 997532216 39361909 75179876 816005324 115649482 801539169 70138016 95888199 892467950 979656965 761391537 354528877 519086852 35676822 910063828 301582400 261610070 73340896 342686965 835379442 186930971 778389960 245321804 936904477 365427914 691461347 321579617 593870684 545240614 874770591 494238628 393533533 914132499 418423560 211294504 878787036 221718376 281432519 823680290 115941973 111850187 435832530 319475906 630937038 471509352 80300437 932519437 733119421 153641332 125967105 419259567 340572302 904357065 664581370 128237482 120545682 206803421 449817099 563421421 752044034 175348393 59415697 147333214 91236540 326844312 207632773 819028631 548562687 338070347 493469625 513509716 449920533 929302154 681990677 929862626 251572209 762291113 713142767 833696686 915932444 839109871 254711900 107265449 594227639 768298325 235502930 563778377 975101745 685320028 128955445 577906482 860668421 37376197 574244751 800910016 364220508 630882579 470699350 761788251 968952925 813174030 126058670 269634161 593236888 808049346 201252435 844809096 572096106 914395201 529266485 338789253 604265775 783978384 295059757 49254118 403037413 530562686 613032494 228899861 66643418 590992994 806806343 776316894 628369191 231811797 427987613 841594754 862694376 898686962 605138652 682408004 562621696 731197321 952042165 157614231 390007370 4055303 851428382 962103475 918450503 382450515 151653431 373476981 17189602 446713187 271736154 420227014 826280929 884768647 649126875 892924346 326522345 306693921 520001943 954891535 387510773 947989555 647246992 100965852 697437220 103146348 783373856 261814563 834343668 737171668 268433849 75111742 741226970 121617879 38970864 510438176 353073449 39629351 732920212 370263050 335347593 6412014 639495120 163384169 740185716 139382698 905313570 68463708 446076618 427071160 872360298 833587390 225821418

输出样例 #2

521800668

说明

令 $i$ 表示大小为 $i$ 的原连通块，我们在连通块之间的连边有以下三种可能: - $2-3-4$ - $3-2-4$ - $2-4-3$ 价值和为: $$(2×3^2 ×4×2+3×2^2 ×4×2+2×4^2 ×3×2)×(1+2+1)=1728$$ --- 本题共有 $20$ 个测试点，每个测试点 $5$ 分。 - $20\%$ 的数据中，$n\le500$。 - 另外 $20\%$ 的数据中，$n \le 3000$。 - 另外 $10\%$ 的数据中，$n \le 10010, m = 1$。 - 另外 $10\%$的数据中，$n \le 10015,m = 2$。 - 另外 $20\%$ 的数据中，所有 $a_i$ 相等。 - $100\%$ 的数据中，$n \le 3\times 10^4,m \le 30$。其中，每一个部分分的测试点均有一定梯度。