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

本文主要是介绍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）- 压力测试赛题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！