计数题选做
[ABC267G] Increasing K Times
Difficulty: *2561。
题目所求即为重排 \(a\)，使得满足 \(a_i<a_{i+1}\) 的下标 \(i\) 恰有 \(k\) 个的方案数。
容易发现，\(a\) 的顺序其实没有影响，可以直接先将 \(a\) 排序。
设 \(dp_{i,j}\) 表示前 \(i\) 个数，恰有 \(j\) 个下标满足 \(a_k<a_{k+1}\) 的方案数，考虑将 \(a_i\) 插入，则可能会产生两种贡献：
- 若将 \(a_i\) 插在某个顺序对中间，则该顺序对中较小的元素一定 \(<a_i\)，较大的元素一定 \(\ge a_i\)，此时顺序对个数变化 \(+1-1=0\)。
- 若将 \(a_i\) 插在某个非顺序对中间，假设其为 \(a_p,a_{p+1}\)（\(a_p\ge a_{p+1}\)）。
- 若 \(a_p =a_i\ge a_{p+1}\)，此时顺序对个数没有变化；
- 若 \(a_p<a_i>a_{p+1}\)，此时顺序对个数 \(+1\)。
- 若将 \(a_i\) 插在头部，顺序对个数没有变化。
- 若将 \(a_i\) 插在尾部，若 \(a_{i-1}=a_i\) 则顺序对个数不变，否则 \(+1\)。这种情况可以和情况 2 合并。
因此，设此时 \(a_i\) 共出现 \(cnt_i\) 次，则 \(j\) 不变的情况共有 \(j+1+cnt_{a_i}\) 种，\(j\) 增加 \(1\) 的情况共有 \((i+1)-(j+1+cnt_{a_i})\) 种。转移方程：
\[dp_{i,j}=dp_{i-1,j}\cdot(j+1+cnt_{a_i})+dp_{i-1,j-1}\cdot (i-j-cnt_{a_i})
\]
直接转移即可，时间复杂度 \(\mathcal{O}(n^2)\)。
Code
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int _N = 1e5 + 5;
const int MOD = 998244353;
int T;
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n + 1), cnt(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a.begin() + 1, a.end());
vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] += dp[i - 1][j] * (j + 1 + cnt[a[i]]) % MOD;
if (j > 0) dp[i][j] += dp[i - 1][j - 1] * (i - j - cnt[a[i]]) % MOD;
dp[i][j] %= MOD;
}
cnt[a[i]]++;
}
cout << dp[n][k] << '\n';
return;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin >> T;
T = 1;
while (T--) {
solve();
}
}
[CF1612G] Max Sum Array
Difficulty: *2500。
假设 \(i\) 在 \(a\) 中出现的位置分别为 \(p_1,p_2,\dots,p_{c_i}\)（\(p_1<p_2<\cdots<p_{c_i}\)），则产生的总贡献为
\[\sum_{1\le j<k\le c_i} p_k-p_j
\]
对于每项算出贡献，即为
\[\sum_{1\le j\le c_i}(j-1)p_j-(c_i-j)p_j=\sum_{1\le j\le c_i}(2j-c_i-1) p_j
\]
对于 \(a\) 中的单个元素算贡献，可以把前面的 \((2j-c_i-1)\) 看成权值，贪心地把权值小的放在前面即可，方案数即为所有权值相同段长度的阶乘之积。
由于暴力的复杂度和 \(\sum c_i\) 有关，我们可以直接记录每个权值下有多少下标，权值最多有 \(2\cdot \max c_i\) 种，直接扫一遍即可。加的时候可以分奇偶差分，时间复杂度为 \(\mathcal{O}(m+\max c_i)\)。
Code
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int _N = 1e5 + 5;
const int MOD = 1e9 + 7;
int T;
void solve() {
int m; cin >> m;
vector<int> c(m + 1);
int mx = 0;
for (int i = 1; i <= m; i++) cin >> c[i], mx = max(mx, c[i]);
vector<int> bucket(2 * mx + 2);
for (int i = 1; i <= m; i++) {
int s = mx - c[i] + 1, t = mx + c[i] - 1;
bucket[s]++, bucket[t + 2]--;
}
int len = 0;
for (int i = 1; i < 2 * mx; i++) {
if (i > 1) bucket[i] += bucket[i - 2];
len = max(len, bucket[i]);
}
vector<int> fac(len + 1, 1);
for (int i = 1; i <= len; i++) fac[i] = 1ll * i * fac[i - 1] % MOD;
int cnt = 1; ll val = 0, ans = 1;
for (int i = 1; i < 2 * mx; i++) {
val += (1ll * (cnt + cnt + bucket[i] - 1) * bucket[i] / 2) % MOD * (i - mx) % MOD;
val %= MOD;
ans *= fac[bucket[i]];
ans %= MOD;
cnt += bucket[i];
}
cout << val << ' ' << ans << '\n';
return;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin >> T;
T = 1;
while (T--) {
solve();
}
}