Update Max
将总贡献拆成每个位置单独的贡献。
假设一共有 \(m\) 个数未确定。
如果 \(a_i \neq -1\)，那么产生贡献的条件就是：
- 前面每个 \(a_j < a_i\)。
- 前面填充的 \(cnt\) 个空的数都要小于 \(a_i\)。
第一个条件可以直接判断，第二个考虑使用组合数学。由于只能使用那些小于 \(a_i\) 的数，假设一共有 \(x\) 个，那么答案就是 \(A_x^{cnt}\)。而后面的空都可以任意填充，那么贡献还需要乘 \((m-cnt)!\)。总贡献：\(A_x^{cnt} \times (m-cnt)!\)。
如果 \(a_i = -1\)，那么条件可以拆成：
- \(cnt\) 个空(包括自己)中，最大值要大于 \(\max\limits_{1\leqslant j < i} a_j\).
- \(cnt\) 个空中，位于 \(i\) 的空数字最大。
第一个条件似乎不太好求，考虑正难则反，用总情况数(\(A_m^{cnt}\))减去每个数都小于的情况(假设有 \(x\) 个数不合法，那么就是 \(A_x^{cnt}\))。
对于第二个条件，由于最大值在每个位置的情况都是相同的，将贡献除以 \(cnt\) 即可。同上，后面的空可以任意填充，贡献还需要乘 \((m-cnt)!\)。
总贡献：\(\frac{(A_m^{cnt}-A_x^{cnt})\times (m-cnt)!}{cnt}\)。
点击查看代码
#include <bits/stdc++.h>
#define _1 (__int128)1
using namespace std;
using ll = long long;
void FileIO (const string s) {
freopen(string(s + ".in").c_str(), "r", stdin);
freopen(string(s + ".out").c_str(), "w", stdout);
}
const int N = 2e5 + 10, mod = 998244353;
int n, a[N], b[N], m, inv[N], X[N], F[N], ans, mx[N], cnt;
bool f[N];
inline int C (int a, int b) {
return (a >= b ? 1ll * F[a] * X[b] % mod * X[a - b] % mod : 0);
}
inline int A (int a, int b) {
return (a >= b ? 1ll * F[a] * X[a - b] % mod : 0);
}
int qmod (int x, int y) {
int ret = 1;
while (y) ret = (y & 1 ? 1ll * ret * x % mod : ret), x = 1ll * x * x % mod, y >>= 1;
return ret;
}
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
// FileIO("");
cin >> n;
inv[1] = X[0] = F[0] = 1;
for (int i = 2; i <= n; i++)
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for (int i = 1; i <= n; i++)
X[i] = 1ll * X[i - 1] * inv[i] % mod, F[i] = 1ll * F[i - 1] * i % mod;
for (int i = 1; i <= n; i++)
cin >> a[i], f[(a[i] != -1 ? a[i] : 0)] = 1, mx[i] = max(a[i], mx[i - 1]);
for (int i = 1; i <= n; i++)
if (!f[i])
b[++m] = i;
for (int i = 1; i <= n; i++) {
if (a[i] == -1) {
cnt++, ans = (ans + 1ll * (A(m, cnt) - A((lower_bound(b + 1, b + m + 1, mx[i]) - b - 1), cnt)) * A(m - cnt, m - cnt) % mod * qmod(cnt, mod - 2)) % mod;
} else if (a[i] > mx[i - 1]) {
ans = (ans + 1ll * A((lower_bound(b + 1, b + m + 1, a[i]) - b - 1), cnt) * A(m - cnt, m - cnt)) % mod;
}
}
cout << ans;
return 0;
}
Taffy Permutation
令 \(dp_{i,j}\) 表示考虑前 \(i\) 个数，\(s_i=1\) 的位置还有几种选择的情况下一共有多少种合法数组。
- 如果 \(s_i = 1\)，则 \(dp_{i-1,j+1} \xrightarrow{\times (j+1)} dp_{i,j}\)。
- 如果 \(s_i = 0\)，则大致分成两种情况：
- 选择的数字不改变 \(j\)，则有 \(n-i-j+1\) 种选法。
- 选择的数字改变 \(j\)，则 \(\sum\limits_{j+1\leqslant k \leqslant n} dp_{i-1,k} \rightarrow dp_{i,j}\)。
点击查看代码
#include <bits/stdc++.h>
#define _1 (__int128)1
using namespace std;
using ll = long long;
void FileIO (const string s) {
freopen(string(s + ".in").c_str(), "r", stdin);
freopen(string(s + ".out").c_str(), "w", stdout);
}
const int N = 2010, mod = 998244353;
int n, dp[N][N], sum[N][N];
string s;
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
// FileIO("");
cin >> n >> s, s = " " + s, dp[0][n] = 1;
for (int i = 1; i <= n; i++) sum[0][i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (s[i] == '0')
dp[i][j] = (1ll * dp[i - 1][j] * (n - i - j + 1) + sum[i - 1][j + 1]) % mod;
else
dp[i][j] = 1ll * (j + 1) * dp[i - 1][j + 1] % mod;
}
for (int j = n; j; j--) sum[i][j] = (sum[i][j + 1] + dp[i][j]) % mod;
}
cout << dp[n][0];
return 0;
}
Star Divine
注意要处理重边。
有两种做法：随机化和贪心。
随机化：顾名思义，就是随机每个红色星星是否选择，接着判断将每个可选的蓝色星星都选上后星星个数是否足够。
点击查看代码
#include <bits/stdc++.h>
#define _1 (__int128)1
using namespace std;
using ll = long long;
void FileIO (const string s) {
freopen(string(s + ".in").c_str(), "r", stdin);
freopen(string(s + ".out").c_str(), "w", stdout);
}
const int N = 1e5 + 10;
int T, n, m, ed, stk[N], top, stk_[N], top_, ans;
set<int> g[N];
bool f[N];
void Solve () {
mt19937 rnd(time(0));
cin >> n >> m >> ed;
for (int i = 1; i <= n; i++) g[i] = set<int> ();
for (int i = 1, x, y; i <= ed; i++)
cin >> x >> y, g[x].insert(y);
while (1) {
top = top_ = 0;
for (int i = 1; i <= m; i++) {
f[i] = rnd() % 2;
if (f[i])
stk_[++top_] = i;
}
for (int i = 1; i <= n; i++) {
bool cnt = 0;
for (int j : g[i])
cnt ^= f[j];
if (cnt)
stk[++top] = i;
}
if (top + top_ < (n + m + 1) / 2) continue;
cout << top << ' ' << top_ << '\n';
for (int i = 1; i <= top; i++)
cout << stk[i] << ' ';
cout << '\n';
for (int i = 1; i <= top_; i++)
cout << stk_[i] << ' ';
return ;
}
}
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
// FileIO("");
for (cin >> T; T--; Solve(), cout << '\n') {}
return 0;
}
贪心：按照顺序去看每个红色星星是选择还是不选择好，即看做完前 \(i - 1\) 颗红星星的决策后，选择第 \(i\) 颗红星星可以使得哪些蓝星星必然可以选择，而不选择第 \(i\) 颗红星星又可以使得哪些蓝星星必然可以选择，选择两种情况中较大的。容易发现这样必然每次选的星星数量都至少是它可以决定的星星数量的一半，所以可以满足要求。
点击查看代码
#include <bits/stdc++.h>
#define _1 (__int128)1
using namespace std;
using ll = long long;
void FileIO (const string s) {
freopen(string(s + ".in").c_str(), "r", stdin);
freopen(string(s + ".out").c_str(), "w", stdout);
}
const int N = 1e5 + 10;
int T, n, m, ed, stk[N], top, stk_[N], top_, ans, lst[N];
set<int> g[N];
bool f[N];
void Solve () {
cin >> n >> m >> ed, top = top_ = 0;
for (int i = 1; i <= m; i++) g[i] = set<int> ();
for (int i = 1; i <= n; i++) f[i] = 0, lst[i] = 0;
for (int i = 1, x, y; i <= ed; i++)
cin >> x >> y, g[y].insert(x), lst[x] = max(lst[x], y);
for (int i = 1; i <= m; i++) {
int cnt = 1, cnt_ = 0;
for (int j : g[i])
if (i == lst[j])
cnt += !f[j], cnt_ += f[j];
if (cnt > cnt_) {
stk[++top] = i;
for (int j : g[i]) f[j] ^= 1;
}
}
for (int i = 1; i <= n; i++)
if (f[i])
stk_[++top_] = i;
cout << top_ << ' ' << top << '\n';
for (int i = 1; i <= top_; i++)
cout << stk_[i] << ' ';
cout << '\n';
for (int i = 1; i <= top; i++)
cout << stk[i] << ' ';
}
signed main () {
ios::sync_with_stdio(0), cin.tie(0);
// FileIO("");
for (cin >> T; T--; Solve(), cout << '\n') {}
return 0;
}