题解 P7623 [AHOI2021初中组] 收衣服

我还在小学的时候以现在初中名义我大五十牛逼参加了这次，然后身败名裂死磕这道题不会，现在觉得自己好傻啊 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;

}

巴特西

题解 P7623 [AHOI2021初中组] 收衣服

最新文章

热门文章