Codeforces Round 1051 (Div. 2) D1D2題解
D1. Inversion Graph Coloring (Easy Version)
題意：
給定一個序列 \(a_1, a_2, \ldots, a_n\)，我們需要計算其“好”子序列的數量。一個子序列是“好”的，如果存在一種將它的索引染成紅色或藍色的方式，使得對于任何一對索引 \(i < j\) 且子序列中 \(b_i > b_j\)，索引 \(i\) 和 \(j\) 的顏色不同。換句話說，子序列的逆序圖是二分圖。
思路：
經分析，一個子序列是“好”的當且僅當它不包含長度為 3 的遞減子序列（即沒有三個元素 \(b_i > b_j > b_k\) 且 \(i < j < k\)）。因此，問題轉化為計算序列中所有不包含長度為 3 的遞減子序列的子序列的數量
由于 $n \leq 300 $ 且所有測試用例的 $ n $ 總和不超過 300，我們可以使用動態規劃（DP）來高效計數。
DP 狀態設計
定義 DP 狀態 ( dp[j][k] ) 表示當前子序列的最大值為 ( j )、次大值為 ( k ) 的子序列數量。其中 ( j ) 和 ( k ) 是序列中的值（范圍從 0 到 ( n )，0 用于表示空狀態）。初始狀態 ( dp[0][0] = 1 ) 代表空子序列。
狀態轉移
遍歷序列中的每個元素$ ( a_i )$ 時，對于每個狀態 \((j, k)\) ，我們考慮兩種選擇：
- 不選當前元素：狀態不變，即 $ dp[j][k] $ 貢獻到新狀態 $ cp[j][k]$。
- 選當前元素：根據 $ a_i $ 與當前最大值 $ j $ 和次大值 $ k $ 的關系更新狀態：
- 如果 \(( a_i \geq j )\)，添加后新最大值為 ( a_i )，次大值為 ( j )，狀態轉移到 ( cp[a_i][j] )。
- 如果 \(( a_i < j )\) 但 \(( a_i \geq k )\)，添加后最大值不變，次大值更新為 \(( a_i )\)，狀態轉移到 \(( cp[j][a_i] )\)。
- 如果 \(( a_i < k )\)，添加后會形成三個遞減元素 \(( j > k > a_i )\)，因此不能選，跳過。
這樣確保所有計數的子序列都不包含長度為 3 的遞減子序列。
代碼
#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
#define PII pair<int, int>
#define PLL pair<long ,long>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;
const int N = 310;
const int mod = 1e9 + 7;
int t;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// dp[j][k] 表示當前子序列的最大值為 j，次大值為 k 的子序列數量
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
dp[0][0] = 1; // 初始狀態：空子序列
for (int i = 0; i < n; ++i) {
vector<vector<int>> cp(n + 1, vector<int>(n + 1, 0)); // 臨時狀態矩陣
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= n; ++k) {
// 不選當前元素 a[i]
cp[j][k] = (cp[j][k] + dp[j][k]) % mod;
// 選當前元素 a[i]
if (a[i] >= j) {
// 新最大值是 a[i]，次大值是 j
cp[a[i]][j] = (cp[a[i]][j] + dp[j][k]) % mod;
} else if (a[i] >= k) {
// 最大值不變，次大值更新為 a[i]
cp[j][a[i]] = (cp[j][a[i]] + dp[j][k]) % mod;
} else {
// 如果 a[i] < k，添加會形成三個遞減，跳過
continue;
}
}
}
dp = cp; // 更新狀態
}
ll res = 0;
// 求和所有狀態的值
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
res = (res + dp[i][j]) % mod;
}
}
cout << res << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D2. Inversion Graph Coloring (Hard Version)
題意：
同前，でも\(n = 2000\)
思路：
原 \(dp[j][k]\) 表示：已經選的子序列中兩種顏色各自最后一個元素的值（分別記為 \(j\)、\(k\)）。
遍歷新元素 \(v = a[i]\) 時，只會修改兩類位置：行 \(\boxed{j == v}\) （把元素放到顏色1）和列 \(\boxed{k == v}\) （把元素放到顏色2，且 \(j > v\)）。因此不必在每一步重建整個 \(n \times n\) 表格，只需要對這兩類位置做增量更新。
對于行更新需要按列查詢列前綴和：\(\sum_{j=0}^{v} dp[j][k]\)，為此給每一列維護一個 Fenwick（按 \(j\) 的維度做前綴和）。
對于列更新需要按行查詢行前綴和：\(\sum_{k=0}^{v} dp[j][k]\)，為此給每一行維護一個 Fenwick（按 \(k\) 的維度做前綴和）。
每次把增量寫回 \(dp\) 的同時，立刻更新對應的行/列 Fenwick（因為這些增量只會影響未來元素的查詢，但對本次同一列/同行的查詢順序不會產生交叉影響，按上面順序逐項處理即可安全使用）。
代碼
#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
#define PII pair<int, int>
#define PLL pair<long ,long>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;
const int N = 310;
const int MOD = 1e9 + 7;
//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;
//dp[i][j]
struct Fenwick {
int n;
vector<int> bit;
Fenwick() : n(0) {}
Fenwick(int _n) { init(_n); }
void init(int _n) {
n = _n; // we will use positions 0..(n-1) if _n is count
bit.assign(n + 5, 0);
}
// add val to position pos (pos in [0..n-1])
void add(int pos, int val) {
if (val == 0) return;
int i = pos + 1;
while (i <= n) {
bit[i] += val;
if (bit[i] >= MOD) bit[i] -= MOD;
i += i & -i;
}
}
// sum of [0..pos], pos in [-1..n-1]
int sumPrefix(int pos) {
if (pos < 0) return 0;
int i = pos + 1;
int res = 0;
while (i > 0) {
res += bit[i];
if (res >= MOD) res -= MOD;
i -= i & -i;
}
return res;
}
};
void solve() {
int n;
cin >> n;
vector<int> a (n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// dp[j][k], j,k in [0..n]
vector<vector<int> > dp (n + 1, vector<int> (n + 1, 0));
dp[0][0] = 1;
// vec1 = rowFen[j] (for fixed j, prefix over k)
// vec2 = colFen[k] (for fixed k, prefix over j)
vector<Fenwick> vec1 (n + 1), vec2 (n + 1);
for (int i = 0; i <= n; ++i) {
vec1[i].init(n + 1);
vec2[i].init(n + 1);
}
// initial state
vec1[0].add(0, 1);
vec2[0].add(0, 1);
for (int idx = 0; idx < n; ++idx) {
int v = a[idx]; // 1..n
// 1) 把當前元素放到“顏色1”的末尾 -> 更新行 j == v:
// 對每個 k in [0..n]: dp[v][k] += sum_{j=0..v} dp[j][k] (colFen[k].sumPrefix(v))
for (int k = 0; k <= n; ++k) {
int addVal = vec2[k].sumPrefix(v);
if (addVal == 0) continue;
dp[v][k] += addVal;
if (dp[v][k] >= MOD) dp[v][k] -= MOD;
vec1[v].add(k, addVal); // 更新 rowFen[v] 的 k 位置
vec2[k].add(v, addVal); // 更新 colFen[k] 的 j=v 位置
}
// 2) 把當前元素放到“顏色2”的末尾 -> 更新列 k == v，但只有 j > v 才走這條
// 對每個 j in (v..n]: dp[j][v] += sum_{k=0..v} dp[j][k] (rowFen[j].sumPrefix(v))
for (int j = v + 1; j <= n; ++j) {
int addVal = vec1[j].sumPrefix(v);
if (addVal == 0) continue;
dp[j][v] += addVal;
if (dp[j][v] >= MOD) dp[j][v] -= MOD;
vec1[j].add(v, addVal);
vec2[v].add(j, addVal);
}
}
ll res = 0;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
res = (res + dp[i][j]) % MOD;
}
}
cout << res << "\n";
}
signed main() {
ios::sync_with_stdio (false);
cin.tie(NULL);
cout.tie(NULL);
t = 1;
cin >> t;
while (t --) {
solve();
}
return 0;
}
浙公網安備 33010602011771號