021中国大学生程序设计竞赛(CCPC)- 压力测试赛题解

A.Matrix

挺狗的一道题,从开始冲到最后都没冲出来,都没啥思路。
其实分开考虑每个数的贡献,这个想法也存在过,就是不知道该怎么计算,我们考虑我们单独考虑一个数字\(i(1\leq i\leq n)\)的贡献,其实就是在有一行答案是\(i\)的情况下总的方案数有多少个。同时我们注意到,每个不同的数之间是互不冲突的,因为在一个方案中,我们也是每行求每个数的答案然后累加起来。所以我们只考虑一个数在多少个不同的方案里贡献了答案。首先我们要选一行,其次保证这一行的答案是\(i\),考虑到这一行的其他数必须都比它大,也就是\(C_{n^2-i}^{n-1}\)个,其次考虑这一行\(n\)个数的排列,就是\(n!\),还有就是除了这一行,其他所有数的排列。就是\((n^2-n)!\)也就是说单独一个\(i\)的贡献就是\(n*C_{n^2-i}^{n-1}*n!*(n^2-n)!\)所有数的答案就是\(ans=n*n!*(n^2-n)!\sum_{i=1}^{n}C_{n^2-i}^{n-1}\)数据\(n=5000\),随便都可以过。

021中国大学生程序设计竞赛(CCPC)- 压力测试赛题解

上一篇:文件管理基础命令之二


下一篇:腾讯电脑管家