读了读大佬的思路试着写了一下Python的版本,顺便扯些题解
参考题解:https://www.acwing.com/solution/content/137903/
题目描述
这个题目简单来说,就是求1~n的所有排列组合中,存在多少对一个前面的数小于后面的数的情况
例如样例中的n = 3的情况
样例
算法1
总结规律
1,2,3…n 这n个数字中,将不同的两个数字组成一个组,这样的组一共可以组成n*(n-1)/2组,这其中的每一组在每一个排列中都有出现,由于是全排列并且每一个组出现的时候,前者小于后者的概率都是1/2。所以答案就是成对的数字的组的数量 * 全排列的数量 * 1/2
而n个数字的全排列的一共有n!种
答案 = [n*(n-1)]/2 * n! * 1/2
案例分析
时间复杂度
O(n)
Python 代码
mod = 998244353
n = int(input())
if n == 2:
print(1)
exit()
ans = 1
for i in range(3,n+1):
ans = (ans * i) % mod # 计算n!的时候从3开始,少一个*2 来抵消后面的1/2
ans = (ans * ((n * (n - 1) // 2) % mod)) % mod
print(ans)
组成n*(n-1)/2组,作者括号写错了
还真是,谢谢哥们指出🙏
厉害
牛
1,2,3…n 这n个数字中,将不同的两个数字组成一个组,这样的组一共可以组成(nn-1)/2组.当n=3时,(33-1)/2=4不应该是4组么?是漏了括号么?[n*(n-1)]/2这样?
对哦,我写这个题解的时候太粗心了,这都看漏了,谢谢提醒捏