PTZ & ICPC Training Camp Powered by Huawei - 《CSL讲废话》

Day 1
- Problem E
include

Day 1

Problem E

题意

n 个点，m 条边的无向图，边权是 1~m 的排列。统计有多少排列满足前 n - 1条边为这个图的最小生成树。

解法

每一条非树边必须满足的条件是：它的边权必须大于两个顶点在树上的路径的每一条边的边权。于是我们得到了这 m 条边的一个大小关系构成的 DAG。我们需要求的就是这个 DAG 的拓扑序的数量。
拓扑序的数量可以这个可以使用状压 DP 来求。
dp[S] 表示拓扑序中已经出现了的前 n - 1 条边的集合

枚举下一个出现的边转移： dp[ S | {i} ] <- dp[S] * P(count(f({i}) \ f(S)) + count(S + f(S)), count(S + f(S)))，即新加入一条边会引入的可能拓扑序的数量。

这样没有考虑图中的自环（样例3），可以发现，自环可以出现在拓扑序的任何位置，所以最后答案再乘上一个排列数即可。
代码
```cpp
include

using i64 = long long; using u128 = __int128;

const int MOD = 998244353;

const int MAXN = 20; const int MAXM = 100;

int n, m; int arr[MAXM][2]; int dsu[MAXN]; std::vector edges[MAXN]; std::map, int> mp; bool mat[MAXM][MAXM]; int fac[MAXM 2], inv[MAXM 2];

int dp[1 << 19]; u128 fa[1 << 19];

int popcount(u128 x) { return builtin_popcountll(x) + builtin_popcountll(x >> 64); }

i64 pow(i64 x, i64 n, i64 mod) { assert(n >= 0); i64 ret = mod != 1; for (x %= mod; n; n >>= 1, x = x x % mod) if (n & 1) ret = ret x % mod; return ret; }

int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }

int prev[MAXN]; std::vector findPath(int u, int v) { if (u == v) return {u}; for (int i = 0; i < n; ++i) prev[i] = -1; std::queue queue; queue.push(v); prev[v] = v; while (prev[u] == -1) { int x = queue.front(); queue.pop(); for (int y : edges[x]) { if (prev[y] != -1) continue; prev[y] = x; if (y == u) break; queue.push(y); } } std::vector path; for (int x = u; x != v; x = prev[x]) path.push_back(x); path.push_back(v); return path; }

int main() { fac[0] = 1;

for (int i = 1; i < MAXM * 2; i++) {
    fac[i] = i64(fac[i - 1]) * i % MOD;
}
inv[MAXM * 2 - 1] = pow(fac[MAXM * 2 - 1], MOD - 2, MOD);
for (int i = MAXM * 2 - 2; ~i; i--)
    inv[i] = i64(inv[i + 1]) * (i + 1) % MOD;
std::scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
    std::scanf("%d%d", &arr[i][0], &arr[i][1]), --arr[i][0], --arr[i][1];
for (int i = 0; i < n; ++i)
    dsu[i] = i;
bool ok = true;
for (int i = 0; i < n - 1; ++i) {
    int u = find(arr[i][0]), v = find(arr[i][1]);
    if (u == v) {
        ok = false;
        break;
    }
    dsu[v] = u;
    edges[arr[i][0]].emplace_back(arr[i][1]);
    edges[arr[i][1]].emplace_back(arr[i][0]);
    mp[{arr[i][0], arr[i][1]}] = i;
    mp[{arr[i][1], arr[i][0]}] = i;
}
if (!ok)
    std::puts("0");
else {
    int self = 0;
    for (int i = n - 1; i < m; ++i) {
        if(arr[i][0] == arr[i][1]) ++self;
        auto path = findPath(arr[i][0], arr[i][1]);
        for (int j = 0; j < int(path.size()) - 1; ++j) {
            int index = mp[{path[j], path[j + 1]}];
            mat[index][i] = true;
        }
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j < m; j++) {
            if (mat[i][j]) {
                fa[1 << i] |= u128(1) << j;
            }
        }
    }
    for (int i = 0; i < n - 1; i++) {
        dp[1 << i] = fac[popcount(fa[1 << i])];
    }
    for (int S = 1; S < (1 << (n - 1)); S++) {
        int oldNode = popcount(fa[S]) + __builtin_popcount(S);
        for (int i = 0; i < n - 1; i++) {
            if (!(S >> i & 1)) {
                int newNode = popcount(fa[1 << i] & ~fa[S]);
                int cnt = i64(fac[newNode + oldNode]) * inv[oldNode] % MOD;
                dp[S | 1 << i] %= MOD;
                fa[S | 1 << i] |= fa[1 << i];
            }
        }
    }
    int result = dp[(1 << (n - 1)) - 1];
    result = i64(result) * fac[m] % MOD * 
        pow(fac[m - self], MOD - 2, MOD) % MOD;
    std::printf("%d\n", result);
}

}


---
<a name="9Lqvv"></a>
## Day 2
<a name="nqgm7"></a>
### Problem I
> ![image.png](https://cdn.nlark.com/yuque/0/2021/png/8437667/1612526234691-e5a8c9e7-6256-4da5-9587-bc7d180fb17e.png#align=left&display=inline&height=1319&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1319&originWidth=1381&size=175572&status=done&style=none&width=1381)
<a name="gXIzp"></a>
#### 题意
有 n 件物品，每件物品有两个参数 c 和 p，第 k 件买这个物品的时候的价格是 c + kp，问 S 元预算最多能买多少，保证 p 各不相同。
<a name="zoTDW"></a>
#### 解法
如果我们定下要买哪 k 件，那么最好的策略一点是按 p 从大到小地去购买。可以发现，由于 p 各不相同，所以买 k 件物品的最少花费 (k - 2) (k - 1) k / 6，所以可行的 k 不会很大，我们可以直接 DP。按 p 降序排，dp[i][j] 表示 前 i 件物品买了 j 件的最小花费。第一维滚掉就是个普通的 01 背包。
<a name="D7GHW"></a>
#### 代码
```cpp
#include <bits/stdc++.h>
using i64 = long long;
const int MAXN = 100005;
std::pair<int, int> a[maxn];
i64 dp[2][maxn];
int main() {
    int n, S;
    scanf("%d%d", &n, &S);
    for (int i = 0; i < n; i++) scanf("%d", &a[i].second);
    for (int i = 0; i < n; i++) scanf("%d", &a[i].first);
    sort(a, a + n, greater<std::pair<int, int>>());
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    for (int i = 0; i < n; i++) {
        int id = i & 1;
        for (int j = 0; j < 3000; j++) {
            dp[id][j] = dp[id ^ 1][j];
            if (j > 0)
                dp[id][j] = std::min(dp[id][j], dp[id ^ 1][j - 1] + a[i].second +
                                               1LL * a[i].first * (j - 1));
        }
    }
    int id = (n - 1) & 1;
    for (int i = 0; i < 3000; i++) {
        if (dp[id][i] > S) {
            printf("%d\n", i - 1);
            break;
        }
    }
}