[洛谷P5216]DLS 采花

题目大意：有$n$个数，任意排列，排列后第$i$个数会产生贡献当且仅当$1sim i-1$中的数不是它的因子，问所有排列的贡献和

题解：发现一个数要产生贡献要求所有它的因子在它的右边，设有$cnt_i$个数是它的因子，这个数就会出现$dfrac{n!}{cnt_i+1}$次（这个数在这$cnt_i+1$个数中出现位置任意，但被钦定在第一个）。算一下贡献就可以了

卡点：无

C++ Code：

#include <cstdio>
#define N 100010
#define maxn N
const int mod = 998244353;

int n, prod = 1;
int s[maxn], cnt[maxn], inv[maxn];
int main() {
	scanf("%d", &n);
	inv[0] = inv[1] = 1;
	for (int i = 2, x; i <= n + 1; ++i) {
		scanf("%d", &x);
		++cnt[x];
		inv[i] = static_cast<long long> (mod - mod / i) * inv[mod % i] % mod;
		prod = static_cast<long long> (i - 1) * prod % mod;
	}
	long long ans = 0;
	for (int i = 1; i < N; ++i) if (cnt[i]) {
		for (int j = i; j < N; j += i) s[j] += cnt[i];
		(ans += static_cast<long long> (inv[s[i]]) * cnt[i] % mod * i) %= mod;
	}
	printf("%lld
", ans * prod % mod);
	return 0;
}