AtCoder Regular Contest 104

比赛链接

B - DNA Sequence

Description

给出一个长为 $N$ 的字符串，问 A 的个数等于 T 的个数 且 C 的个数等于 G 的个数 的子串有多少个。

Solution

由于 $N \le 5000$，因此可以 $N^2$ 枚举子串的左右端点，利用前缀和容易判断是否满足 $A=T∧C=G$。

另外，这题可以利用 $map$ 优化，对每个位置记录前缀 $A$ 与 $T$ 的个数差 $x$、$C$ 与 $G$ 的个数差 $y$，那么以当前位置结尾的合法子串的开头减 1 处有相同的 $(x,y)$，所以每次在 $map$ 中查询二元组 $(x,y)$ 的数量即可。时间复杂度 $O(NlogN)$。

Code

DNA Sequence

#include <bits/stdc++.h>

using namespace std;

string s;
int ans, n;
map<pair<int, int>, int> mp;

signed main() {
    cin >> n >> s;
    mp[make_pair(0, 0)] = 1;
    int x = 0, y = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'A')
            x++;
        else if (s[i] == 'T')
            x--;
        else if (s[i] == 'C')
            y++;
        else
            y--;
        ans += mp[make_pair(x, y)];
        mp[make_pair(x, y)]++;
    }
    cout << ans;
    return 0;
}

C - Fair Elevator

Description

1 个 $2N$ 层的建筑中有 $N$ 个人搭乘电梯，需要满足以下两个条件：

• 设每个人上下电梯的楼层为 $A_i,B_i$，且 $A_1,B_1,A_2,B_2...A_N,B_N$ 互不相同。
• 同一时刻在电梯中的人 $B_i-A_i$ 都相同。

现给出 $A,B$ 数组，但其中有一部分信息丢失（用 -1 表示），且有可能存在错误信息，问补上丢失的信息后是否有可能满足上述条件。

Solution

首先特判有重复楼层或者 $A_i>B_i(A_i,B_i \neq -1)$ 的情况，这两种情况无解。

设一个人在第 $x$ 层上，在 $x+k$ 层下，且在 $x$ 层时电梯中只有这一人，那么对 $\forall v∈[x+1,x+k-1]$，都存在 $A_i=v ∧ B_i=A_i+k$，即楼层 $[x,x+2k-1]$ 的上下电梯情况都能被确定。

由上述分析可知，存在合法情况当且仅当可以将楼层分成若干个长度为偶数（设为 $2k$ ）的段，每段满足恰有 $k$ 个人在这个段的前半部分的不同楼层上电梯，并在 $k$ 层之后下电梯。设 $dp[i]$ 表示前 $i$ 层（$i$ 为偶数）能否满足条件，枚举长度 $2k$，如果区间 $[i+1,i+2k]$ 合法且 $dp[i]=1$，那么 $dp[i+2k] =1$。最后如果 $dp[2n]=0$ 则无解。

上述状态转移的时间复杂度为 $O(n^3)$

Code

Fair Elevator

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 105;

int n, a[MAXN], b[MAXN];
bool vis[MAXN * 2], dp[MAXN * 2];

signed main() {
    cin >> n;
    bool tag = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        if (a[i] != -1) vis[a[i]] ? tag = 0 : vis[a[i]] = 1;
        if (b[i] != -1) vis[b[i]] ? tag = 0 : vis[b[i]] = 1;
        if (a[i] > b[i] && b[i] != -1) tag = 0;
    }
    if (!tag) return cout << "No", 0;
    dp[0] = 1;
    for (int i = 0; i <= 2 * n; i += 2) {
        for (int len = 2; i + len <= 2 * n; len += 2) {
            bool tag = 1;
            int halflen = len / 2;
            int f[MAXN * 2] = {0};
            for (int j = 1; j <= n; j++) {
                if (b[j] != -1) {
                    if (i + 1 <= b[j] && b[j] <= i + halflen) {
                        tag = 0;
                        break;
                    } else if (i + 1 + halflen <= b[j] && b[j] <= i + len) {
                        if (f[b[j]] || f[b[j] - halflen]) {
                            tag = 0;
                            break;
                        } else
                            f[b[j]] = f[b[j] - halflen] = j;
                    }
                }
                if (a[j] != -1) {
                    if (i + 1 + halflen <= a[j] && a[j] <= i + len) {
                        tag = 0;
                        break;
                    } else if (i + 1 <= a[j] && a[j] <= i + halflen) {
                        if ((f[a[j]] && f[a[j]] != j) ||
                            (f[a[j] + halflen] && f[a[j] + halflen] != j)) {
                            tag = 0;
                            break;
                        } else
                            f[a[j]] = f[a[j] + halflen] = j;
                    }
                }
            }
            if (dp[i] && tag) dp[i + len] = 1;
        }
    }
    cout << (dp[2 * n] ? "Yes" : "No");
    return 0;
}

D - Multiset Mean

Description

求用 $1$ 到 $N$ 之间的数，每个数使用次数不超过 $K$，构成平均值为 $x(1 \le x \le N$) 的非空可重集的方案数。答案对 $M$ 取模。

Solution

设 $cnt_i$ 表示数 $i,i∈[1,N]$ 被选的次数，那么集合中数的平均值为 $x$ 等价于 $\sum\limits_{i=1}^{N}(i-x)cnt_i=0$。因此问题转变为从 $[1,x-1]$ 和 $[1,N-x]$ 这两个区间中分别选择一些数，每个数被选择次数不超过 $K$，使得从这两个区间中选出的数的和相等。

设 $dp[i][s]$ 表示从 $[1,i]$ 选取一些数，每个数被选择次数不超过 $k$，且和为 $s$ 的方案数，那么使平均值为 $x$ 的方案数为 $\sum\limits_{s=0}^{MaxSum} k*dp[x-1][s]*dp[N-x][s]$。接下来考虑如何求 $dp[i][s]$。显然有 $dp[i][s]=\sum\limits_{j=0}^{k}dp[i-1][s-j*i]$。由于 $MaxSum$ 是 $n^2k$ 数量级的，直接枚举 $j$ 的话复杂度是 $O(n^3k^2)$的，时限 $4s$ 卡卡常还是能过的。注意到 $\sum\limits_{j=0}^{k}dp[i-1][s-j*i]$ 可用前缀和维护，因此不用枚举 $j$，从而时间复杂度降至 $O(n^3k)$。

Code

Multiset Mean

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 101;

int n, m;
LL k, f[101][130005], sum[130005];
LL ans[101];

void add(LL& a, LL b) { a = ((a + b) % m + m) % m; }

signed main() {
    cin >> n >> k >> m;
    ans[1] = k;

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        memset(sum, 0, sizeof(sum));
        int lim = min((n + 1) / 2 - 1, i);
        lim = k * (1 + lim) * lim / 2;
        for (int s = 0; s <= lim; s++)
            add(sum[s], (s - i >= 0 ? sum[s - i] : 0) + f[i - 1][s]);
        for (int s = 0; s <= lim; s++)
            add(f[i][s],
                sum[s] - (s - (k + 1) * i >= 0 ? sum[s - (k + 1) * i] : 0));
    }

    for (int x = 2; x <= (n + 1) / 2; x++) {
        int lim = k * x * (x - 1) / 2;
        for (int i = 1; i <= lim; i++)
            add(ans[x], f[x - 1][i] * f[n - x][i] % m * (k + 1));
        add(ans[x], k);
    }

    for (int i = 1; i <= n; i++) {
        if (i <= (n + 1) / 2)
            cout << ans[i] << endl;
        else
            cout << ans[n - i + 1] << endl;
    }
    return 0;
}

E - Random LIS

Desciption

$N$ 个数的序列，第 $i$ 个整数在 $[1,A_i]$ 间等概率随机选取，求该序列最长上升子序列长度的期望

Solution

设 $cnt_i$ 表示使最长公共子序列的长度为 $i$ 的方案数，显然答案为 $\frac{\sum\limits_{i=1}^{N}cnt_i*i}{\prod\limits_{i=1}^{N}A_i}$。

对于分子，我们可以 $O(N^N)$ 暴搜处理 $N$ 个数的相对大小关系（$N \le 6$ 时不同的相对大小关系不超过 4683 个），根据相对大小关系容易求得最长上升子序列的长度，接下来只需考虑求构成该相对大小关系的方案数。

设相对大小最大为 $k$, 第 $i$ 个数相对大小为 $r_i$， $lim_r$ 表示相对大小为 $r$ 的数能取到的最大值，则 $lim_i = \min\limits_{r_j=i}A_j$。现在问题转化成求长度为 $k$, 且 $val_i \le lim_i(1 \le i \le k)$ 的严格上升序列的个数。这是一个经典问题，可以用动态规划求解。

具体的，将 $lim$ 按值域分成 $m$ 段，每段的右端点对应一个 $lim$ 值，同时设 $lim_i$ 属于第 $seg_i$ 段（$seg_0=0$）。设 $dp[i][j]$ 表示将前 $i$ 项构成严格上升序列，最后某几项选择的值属于第 $j$ 段的方案数。显然答案为 $\sum\limits_{i=1}^{seg_k}dp[k][i]$, 且有 $dp[0][0]=1$。接下来考虑状态转移，易得 $dp[i][j]=\sum\limits_{p=0}^{i-1}\sum\limits_{q=0}^{min(seg_p,j-1)}dp[p][q]*C_{len_j}^{i-p}$，这里需要满足 $\forall p'∈[p+1,i],seg_{p'}>=j$。直接转移的话时间复杂度为 $O(N^4)$，本题数据小可以通过。另外，我们可以通过对第二维记录前缀和将时间复杂度降至 $O(N^3)$，代码中 $dp[i][j]$ 表示将前 $i$ 项构成严格上升序列，最后某几项选择的值不超过第 $j$ 段的方案数。

Code

Random LIS

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MOD = 1E9 + 7;
int n, a[7], x[7];
int tot(1), ans(0);
bool vis[654325];

int qpow(int a, int b) {
    int ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void add(int& a, int b) { a = (a + b) % MOD; }

int getLIS(int* rank) {
    int f[7] = {0}, len = 0;
    for (int i = 1; i <= n; i++) {
        int id = lower_bound(f + 1, f + len + 1, rank[i]) - f;
        f[id] = rank[i];
        len = max(len, id);
    }
    return len;
}

int Comb(int n, int m) {
    if (n < m) return 0;
    int num = 1, dem = 1;
    for (int i = n - m + 1; i <= n; i++) num = (num * i) % MOD;
    for (int i = 1; i <= m; i++) dem = (dem * i) % MOD;
    return num * qpow(dem, MOD - 2) % MOD;
}

int seg[7], l[7], r[7];

int DP(int k) {
    int dp[7][7] = {0};
    for (int i = 0; i <= k; i++) dp[0][i] = 1;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= seg[i]; j++) {
            for (int p = i - 1; p >= 0; p--) {
                add(dp[i][j], dp[p][min(seg[p], j - 1)] *
                                  Comb(r[j] - l[j] + 1, i - p) % MOD);
                if (seg[p] < j) break;
            }
            add(dp[i][j], dp[i][j - 1]);
        }
    return dp[k][seg[k]];
}

int solve() {
    int rank[7] = {0}, lim[7] = {0}, state = 0;
    vector<int> v;
    for (int i = 1; i <= n; i++) rank[i] = x[i], v.push_back(rank[i]);
    sort(v.begin(), v.end());
    auto last = unique(v.begin(), v.end());
    for (int i = 1; i <= n; i++) {
        rank[i] = lower_bound(v.begin(), last, rank[i]) - v.begin() + 1,
        state = state * 10 + rank[i];
        lim[rank[i]] = lim[rank[i]] ? min(lim[rank[i]], a[i]) : a[i];
    }
    if (vis[state]) return 0;
    vis[state] = 1;

    int k = last - v.begin();
    v.clear();
    for (int i = 1; i <= k; i++) v.push_back(lim[i]);
    sort(v.begin(), v.end());
    last = unique(v.begin(), v.end());
    for (int i = 1; i <= k; i++) {
        int id = lower_bound(v.begin(), last, lim[i]) - v.begin();
        seg[i] = id + 1;
        l[id + 1] = ((id > 0) ? v[id - 1] : 0) + 1;
        r[id + 1] = v[id];
    }
    return DP(k) * getLIS(rank) % MOD;
}

void dfs(int now) {
    if (now == n + 1) {
        add(ans, solve());
        return;
    }
    for (int i = 1; i <= n; i++) {
        x[now] = i;
        dfs(now + 1);
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], tot = tot * a[i] % MOD;
    tot = qpow(tot, MOD - 2);
    dfs(1);
    cout << ans * tot % MOD;
    return 0;
}

F - Visibility Sequence

Description

$n$ 个数，每个数 $H_i$ 的取值在 $[1,X_i]$。设 $P_i$ 表示 $i$ 左侧第一个大于 $H_i$ 的位置，没有为 -1。问能构成多少个不同的数列 $P$ 。

Solution

考虑一个由 $i$ 向 $P_i$ 连边构成的图，有下面两种情况：

1. 设对于区间 $[l,r]$，满足 $\forall j∈[l+1,r], H_l>H_j$，同时 $H_l \le H_{r+1}$，那么下标在 $[l+1,r]$ 的点都会直接或间接地向 $l$ 连边。对于区间 $[l+1,r]$ 可以继续划分出一系列满足上述条件的子区间，这些子区间彼此不交，并起来是 $[l+1,r]$。最后，我们可以得到以 $l$ 为根的树，每个节点的子树对应一段连续的区间。同时，对于每个节点，其值严格大于其儿子的值。

2. 设区间 $[l,r]$ 的最大值为 $x$，那么该区间可以按 $x$ 划分为多个 1 中描述的区间。每个区间对应一棵树，那么我们得到一个森林，森林中每颗树的根的权值不超过 $x$。

设 $dpTree[l][r][x]$ 表示将 $[l,r]$ 组织成一棵树，$l$ 为根，其权值为 $x$ 的方案数，$dpForest[l][r][x]$ 表示将 $[l,r]$ 组织成一片森林，每棵树是一段子区间，所有树根的权值的最大值为 $x$ 的方案数。显然，不同的 $P$ 对应不同的森林，那么问题转化为求将 $[1,n]$ 组织成一片森林的方案数, 即 $\sum\limits_{x=1}^{n}dp[1][n][x]$。这里 $x$ 上限为 $n$ 是因为我们只需要将叶子节点设为 1，之后每往上一层节点的值都加 1，最后每个节点的值都不超过 $n$。显然，我们可以选择更大的值，但这样做并不会增加方案数，因此贪心地对每个节点设置最小值即可。此外，不妨设每个节点的儿子对应数组中下标递增，那么它们的值从左往右不降，否则会连边。

根据前面的分析容易推出如下状态转移方程：

1. $dpTree[l][r][x]=dpForest[l+1][r][x-1]$

2. $dpForest[l][r][x]=dpTree[l][r][x]+\sum\limits_{k=l}^{r-1}\sum\limits_{m=1}^{x}dpForest[l][k][m]*dpTree[k+1][r][x]+\sum\limits_{k=l}^{r-1}\sum\limits_{m=1}^{x-1}dpForest[l][k][x]*dpTree[k+1][r][m]$ (两种情况，一种是增加一颗树，另一种是接到最右边的树上)

直接转移时间复杂度是 $O(n^5)$ 的，但可以通过前缀和将时间复杂度降至 $O(n^4)$。

Code

Visibility Sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MOD = 1E9 + 7;
const int MAXN = 105;

int n, h[MAXN];
LL dpTree[MAXN][MAXN][MAXN], dpForest[MAXN][MAXN][MAXN];
LL sumTree[MAXN][MAXN][MAXN], sumForest[MAXN][MAXN][MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i], h[i] = min(h[i], n);
    for (int i = 1; i <= n; i++) {
        dpTree[i][i][1] = dpForest[i][i][1] = 1;
        for (int j = 1; j <= n; j++) sumTree[i][i][j] = sumForest[i][i][j] = 1;
    }
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int x = 1; x <= h[l]; x++)
                dpTree[l][r][x] = dpForest[l + 1][r][x - 1];
            for (int x = 1; x <= n; x++) {
                dpForest[l][r][x] = dpTree[l][r][x];
                for (int k = l + 1; k <= r; k++) {
                    if (x > h[k]) continue;
                    dpForest[l][r][x] =
                        (dpForest[l][r][x] +
                         dpForest[l][k - 1][x] * sumTree[k][r][x - 1] +
                         sumForest[l][k - 1][x] * dpTree[k][r][x]) %
                        MOD;
                }
                sumTree[l][r][x] =
                    (sumTree[l][r][x - 1] + dpTree[l][r][x]) % MOD;
                sumForest[l][r][x] =
                    (sumForest[l][r][x - 1] + dpForest[l][r][x]) % MOD;
            }
        }
    }
    cout << sumForest[1][n][n];
    return 0;
}