我还在小学的时候以现在初中名义我大五十牛逼参加了这次，然后身败名裂死磕这道题不会，现在觉得自己好傻啊 233333
显然这是要统计每个区间的贡献，所以我们可以打出来这个暴力，统计每个区间的次数，对于 \(n = 5\) 的情况可得
[1,1] 24 [1,2] 24 [1,3] 24 [1,4] 24 [1,5] 24
[2,2] 30 [2,3] 30 [2,4] 30 [2,5] 30
[3,3] 40 [3,4] 40 [3,5] 40
[4,4] 60 [4,5] 60
\([l, r]\) 代表区间，后面的代表贡献次数。
然后下面的操作比较人类智慧，我当时也是突发奇想才想到的规律。
首先我们发现每一行的次数都是一样的，我们把它写成一个数列 \(24,30,40,60,120\)。然后我们就丢到 OIES 上找但是找不到我们不难发现 \(24 = 4! = 4 \times 3 \times 2\times 1\)。
下一个数字是 \(30\)，我们写成类似形式。
\(30 = 3\times 10 = 5\times 3 \times 2 = 5\times 3 \times 2\times 1\)。
再下一个是 \(40\)，类似形式 \(40 = 5 \times 4\times 2 \times 1\)。同理 \(60 = 5\times 4\times 3 \times 1, 120 = 5\times 4\times 3\times 2\)。
列一张表
n = 5
24=4*3*2*1
30=5*3*2*1
40=5*4*2*1
60=5*4*3*1
发现了什么？对于第一行，是 \((n – 1)!\)。第二行是 \(\dfrac{(n – 1)!}{n – 1}\times n\)，第三行是 \(\dfrac{(n – 1)!}{n – 2}\times n\)。
总而言之，第 \(k\) 行，次数是 \(\dfrac{(n – 1)!}{n – k + 1}\times n = \dfrac{n!}{n – k +1}\)。
然后就是非常简单的东西了，统计每行的和，然后按照上面的次数乘一下就行了。
//SIXIANG
#include <iostream>
#define MAXN 500
#define LL long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
const LL Mod = 998244353;
LL w[MAXN + 10][MAXN + 10], frac[MAXN + 10], sum[MAXN + 10];
LL qmul(LL n, LL m) {
LL res = 0;
while(m) {
if(m & 1) res = (res + n) % Mod;
n = (n + n) % Mod, m >>= 1;
}
return res;
}
LL qpow(LL n, LL m) {
LL res = 1;
while(m) {
if(m & 1) res = qmul(res, n) % Mod;
n = qmul(n, n) % Mod, m >>= 1;
}
return res;
}
int main() {
int n; cin >> n;
frac[0] = 1;
for(int p = 1; p <= n; p++)
frac[p] = (frac[p - 1] * p) % Mod;
for(int p = 1; p < n; p++)
for(int i = p; i <= n; i++)
cin >> w[p][i], sum[p] = (sum[p] + w[p][i]) % Mod;
LL ans = 0;
for(int p = 1; p < n; p++)
ans = (ans + qmul(sum[p], qmul(frac[n], qpow((n - p + 1), Mod - 2)))) % Mod;
cout << ans << endl;
}
原文地址：http://www.cnblogs.com/thirty-two/p/16927680.html
