Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 Div. 2)

补题链接：Here

1523A. Game of Life

生命游戏定义

本题中改编为一维坐标上的生命游戏

即使 #card=math&code=m%28m%5Cin%5B1%2C1e9%5D%29) 的范围很大，但每次进化不会超过 次，因为如果我们进化结果与上一代是相同的则说明游戏结束了，但我们只有 格。所以最多进行 次进化迭代

所以我们可以直接模拟进化过程

时间复杂度：#card=math&code=%5Cmathcal%7BO%7D%28n%5E2%29)

void solve() {
    int n; ll m;
    string s;
    cin >> n >> m >> s;
    s = "0" + s + "0";
    while (m--) {
        string t = s;
        for (int i = 1; i <= n; ++i)
            t[i] |= s[i - 1] ^ s[i + 1];
        if (t == s)break;
        s = t;
    }
    cout << s.substr(1, n) << "\n";
}

1523B. Lord of the Values

现有两种操作：选定两个元素（#card=math&code=i%5Cnot%3Dj%5C%20%5Cin%281%2Cn%29) ) ， 并且 为偶数

现在希望执行最多 次操作使得

这里读者可以手写模拟一下，要将任何一对数字 #card=math&code=%28a%2Cb%29) 转换为一对 #card=math&code=%28-a%2C-b%29) ，可以执行一系列操作，例如 #card=math&code=%281%2C2%2C1%2C2%2C1%2C2%29)，同时 为偶数，所以我们可以直接对 #card=math&code=%281%2Cn%29) 的元素如上操作

时间复杂度：#card=math&code=%5Cmathcal%7BO%7D%28n%29)

using ll = long long;
void solve() {
    int n; cin >> n;
    vector<ll>a(n + 1);
    for (int i = 1; i <= n; ++i)cin >> a[i];// 这里可以不用存，伪读入即可
    cout << n * 3 << '\n';
    for (int i = 1; i <= n; i += 2) {
        cout << "1 " << i << " " << i + 1 << '\n';
        cout << "2 " << i << " " << i + 1 << '\n';
        cout << "1 " << i << " " << i + 1 << '\n';
        cout << "2 " << i << " " << i + 1 << '\n';
        cout << "1 " << i << " " << i + 1 << '\n';
        cout << "2 " << i << " " << i + 1 << '\n';
    }
}

1523C. Compression and Expansion

有一个任务表，其中任务里也会嵌套任务，现在由于某些原因任务表出现问题，需要由我们恢复

发现输入的是标题末尾数字，要将完整标题输出。

这道题需要用 STL 构建堆栈。

在堆栈中维护列表的当前深度。 最初堆栈是空的。 对于每个新的 ，有两个选项：

• ： 我们只需将给定的数字添加到堆栈的末尾，它将指向列表中的一个新子项。
• ： 我们需要找到子项，它的最后一个数字将比 小 1。 为此，我们将从堆栈中删除最后一个元素，直到找到这个数字。

在每次迭代结束后，我们将打印结果堆栈作为列表中的新项目。 请注意，由于输出整个列表，复杂度将是二次的。

时间复杂度：#card=math&code=%5Cmathcal%7BO%7D%28n%5E2%29)

void solve() {
    int n; cin >> n;
    vector<int>a;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        if (x > 1) {
            while (!a.empty() && a.back() + 1 != x)
                a.pop_back();
            assert(!a.empty());
            a.pop_back();
        }
        a.push_back(x);
        for (int j = 0; j < (int) a.size(); j++) {
            if (j > 0) {
                cout << ".";
            }
            cout << a[j];
        }
        cout << '\n';
    }
}

1523E. Crypto Lights

概率证明题

让我们考虑设备的所有状态，其中 p 灯打开，以及当前算法尚未完成工作的时间。 我们将检查 p 从 1 到 n 的所有值。

请注意，对于 p 灯打开的状态，到达该状态的概率为 …(n-p-1)%7D#card=math&code=%5Cfrac%7Bp%21%7D%7Bn%2A%28n-1%29…%28n-p-1%29%7D) 。 现在对于 p 的新值，我们需要计算拟合状态的数量。 如果没有灯光之间距离为 k 的条件，这个数字将等于将灯光分成 p 组的方法数，即 #card=math&code=C%28n-1%2Cp-1%29)

接下来我们可以注意到，每个组还必须包含 个元素以提供必要的距离。 那么选择组排列所需的“空闲”单元的数量将是 %E2%8B%85(p-1)#card=math&code=n-%28k-1%29%E2%8B%85%28p-1%29)。 那么最终的排列数量将是 %E2%8B%85(p-1)%2Cp-1)#card=math&code=C%28n-%28k-1%29%E2%8B%85%28p-1%29%2Cp-1%29)。 这些数量的最终总和乘以获得每个数量的概率就是答案。

using ll = long long;
const int N = 1e5 + 10, P = 1e9 + 7;
ll n, k, ans, fac[N], inv[N];
ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1) ans = ans * a % P;
    return ans;
}
void initC() {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % P;
    inv[n] = qpow(fac[n], P - 2);
    for (int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % P;
}
ll C(ll n, ll m) {
    if (n < m) return 0;
    return fac[n] * inv[m] % P * inv[n - m] % P;
}
void solve() {
    cin >> n >> k;
    initC();
    ans = 1;
    for (int i = 1; (i - 1) * (k - 1) <= n; ++i)
        ans = (ans + C(n - (i - 1) * (k - 1), i) * qpow(C(n, i), P - 2) % P) % P;
    cout << ans << "\n";
}