2023/10/15 模拟赛总结

没考，\(0+0+0+0=0\)。

T1 - tv

ST表＋单调栈。

代码还在调。

T2 - card

不会，好像要权值线段树。

T3 - mo

ez，运用同余即可。

// J2023 | BLuemoon_
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5;

int n, d, s[kMaxN], ans, c;

int main() {
  cin >> n >> d;
  for (int i = 1, x; i <= n; i++) {
    cin >> x;
    s[i % d] += x;
  }
  for (int i = 0; i < d; i++) {
    ans += s[i], c = max(c, s[i]);
  }
  cout << ans - c << '\n';
  return 0;
}

T4 - set

考虑集合为 \(\{[1,n] \cap \mathbb{N}\}\)，所以子集和的范围是 \([1,\frac{n \times(n + 1)}{2}]\)，所以用 \(\text{dp}\) 求出每一个和出现的次数 \(\text{dp}_i\)，答案就是 \(\prod i^{\text{dp}_i}\)。但是这里不能取模，于是我们充分发扬人类智慧，所以我们使用费马小定理：当 \(\gcd(a,p) = 1\) 且 \(p\) 为质数时，\(a^{p-1} \equiv 1 \ \ (\!\bmod p)\)。于是我们在更新 \(\text{dp}\) 数组时取模 \(998244352\)，求答案时再取模 \(998244353\) 即可。

// J2023 | BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e2 + 5;
const LL P = 998244353;

LL n, dp[kMaxN * kMaxN] = {1}, ans = 1;

LL C(LL a, LL b) {
  LL ans = 1;
  for (; b; (b & 1) && ((ans *= a) %= P), (a *= a) %= P, b >>= 1) {
  }
  return ans % P;
}
LL Q(LL x) {
  return x * (x + 1) >> 1;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = Q(n); j - i >= 0; j--) {
      (dp[j] += dp[j - i]) %= (P - 1);
    }
  }
  for (LL i = 1; i <= Q(n); (ans *= C(i, dp[i])) %= P, i++) {
  }
  cout << ans << '\n';
  return 0;
}