大致题意:给你一个n * n 的矩阵填充了[1 , n2] 的数,每一行都会贡献一个最小值ai,S = {a1,a2,…,an} ∩ {1,2,…,n} 求ΣS
一行的最小值是1~n中的数时,才对答案有贡献。
首先从1~n枚举一行的最小值 记为i
这一行剩余n-1个数都要比i大,所以有C(n * n - i ,n-1)种选法
然后把这一行的n个数全排列 n!
剩余的n * n - n个数填到剩下的n-1行中,随意排列 共(n * n - n)!种排法
把之前带有i的那一行插进去,组成n行 共n种方法
然后这个排法保证最小值 i 对答案有贡献 即+1
所以有多少排法 答案就加多少
对于每一个 i ,排法有: C(n * n - i ,n-1)* n! * (n * n - n)!* n
则总排法:
for (int i = 1; i <= n; i ++ )
{
int now = C(n * n - i , n - 1) * f[n] % mod * f[n * n - n] % mod * n % mod;///f数组是阶乘数组
res = (res + now) % mod;
}