P7623 题解

Akoasm_X · 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;
}