自动搬运

查看原文

来自洛谷，原作者为

	Akoasm_X AFO|如果我失去了我，那还剩下什么

搬运于2025-08-24 22:31:38，当前版本为作者最后更新于2021-06-21 17:36:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

推不出规律就暴力枚举看一看，枚举全排列，然后按照题意模拟，记录每组交换的次数，输入5发现是这样的，规律就比较明显了

24 24 24 24 24
30 30 30 30
40 40 40
60 60

和题目所给的每个系数相乘，答案刚好是1080。

规律就是 ： 每一行的和是 $n!$ ，并且第$i$行会和$\left[{i},{n}\right]$范围内的数交换，交换次数是相等的。接下来可以借助这个，把每一行的权值求了个平均值，逆元处理，然后再乘$n!$即可，这样做等价于先求$\frac{n!}{n-i+1}$,然后与每个权值相乘。

给出了一个比较感性的证明，全排是 $n!$，对于第1小元素，在每个位置的可能性是相等的，所以每个交换次数就是 $\frac{n!}{n}$。然后考虑第i个元素，每次交换并不影响出现位置的可能性，并且对于第i小的元素，$\left[{1},{i-1}\right]$ 都在前面排好的，所以只会和 $\left[{i},{n}\right]$ 范围内的数交换，具体到每个位置交换次数就是$\frac{n!}{n-i+1}$。

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod  = 998244353;
int n;
LL Ans;

inline LL read() 
{
    LL x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
}

LL qu_pow(LL a,LL k)
{//借助快速幂处理逆元 
	LL ans = 1,base = a;
	while(k)
	{
		if(k&1) ans = (ans * base) % mod;
		base = base * base % mod;
		k >>= 1;
	}
	return ans;
}

int main()
{
	n = read();
	LL fact = 1;for(int i=2;i<=n;i++) fact = fact * i % mod;
	for(int i=1;i<n;i++)
	{
		LL sum = 0;
		for(int j=1;j<=n-i+1;j++)
			sum = (sum + read()) % mod;
		sum = sum * qu_pow(n-i+1,mod-2) % mod;//求解每一行的平均值 
		Ans = (Ans + sum) % mod;
	}
	Ans = Ans * fact % mod;//最后乘排列数 
	printf("%lld\n",Ans);
	return 0;
}