C. Complementary XOR

给定两个长度均为 \(n\) 的 \(\tt{01}\) 串 \(a,b\)，你可以使用下面这种操作：

  • 选择两个下标 \(l,r(1\le l\le r\le n)\)。
  • 对于所有的 \(i\in[l,r]\)，取反 \(a_i\)。
  • 对于所有的 \(i\in[1,l)\cup(r,n]\)，取反 \(b_i\)。

判断是否可以通过使用不超过 \(n+5\) 次操作让两个串里的所有元素都变成 \(00\)。如果可以，输出一种可能的方案。

\(n \leq 2 \times 10^5\)。

考虑连续的两次操作 \([l_1,r_1],[l_2,r_2]\)，简单讨论一下可以发现这相当于将 \(a,b\) 中这两个区间分别取反。

由此可得，如果执行了偶数次操作后 \(a,b\) 均为 \(0\)，那么初始时一定有 \(a=b\)。

类似地，可以得到如果执行了奇数次操作后 \(a,b\) 均为 \(0\)，那么初始时 \(a,b\) 的每一位一定都不同。

然后考虑如何构造：

我们先把所有 \(a_i = 1\) 的位置用一次操作 \([i,i]\) 消掉。

之后根据上面的两种情况，\(b\) 此时可能均为 \(0\) 或均为 \(1\)。如果均为 \(0\) 我们就做完了，否则我们需要用奇数次操作使得 \(a\) 不变。

执行 \([1,1]\)、\([1,2]\)、\([2,2]\) 三次操作就行了。时间复杂度 \(O(n)\)。

code 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
void solve() {
    cin >> n;
    string a, b;
    cin >> a >> b;
    bool same = true, diff = true;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) {
            diff = false;
        } else {
            same = false;
        }
    }
    if (!same && !diff) {
        cout << "NO" << "\n";
        return;
    }
    int one = 0;
    for (int i = 0; i < n; i++)
        if (a[i] == '1') one++;
    if (one % 2 == diff) {
        cout << "YES" << "\n";
        cout << one << "\n";
        for (int i = 0; i < n; i++)
            if (a[i] == '1')
                cout << i + 1 << " " << i + 1 << "\n";
    } else {
        cout << "YES" << "\n";
        cout << one + 3 << "\n";
        cout << 1 << " " << 1 << "\n";
        cout << 2 << " " << 2 << "\n";
        cout << 1 << " " << 2 << "\n";
        for (int i = 0; i < n; i++)
        if (a[i] == '1')
            cout << i + 1 << " " << i + 1 << "\n";
    }
}
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
    return 0;   
}

D. Count GCD

给定 \(n,m\) 和一个数列 \(a\)，求有多少长度为 \(n\) 的序列 \(b\)，使得 \(b_i \in [1,m]\)，且 \(\gcd \limits_{j=1}^i b_j = a_i\)。

答案对 \(998244353\) 取模。

\(n \leq 2 \times 10^5\)，\(m \leq 10^9\)。

显然，如果 \(a_{i} \nmid a_{i-1}\) 那么无解。

容易发现每个位置是独立的，对每个位置分别求出 \(1 \leq x \leq m\) 且 \(\gcd(a_{i-1},x) = a_i\) 的解数即可。

不妨设 \(a_{i} \times p = a_{i-1}\)，则 \(\gcd(a_i \times p, x) = a_i\)，即 \(\gcd(p, \frac{x}{a_i}) = 1\)。

记 \(q = \frac{x}{a_i}\)，要求的就是 \(1 \leq q \leq \lfloor \frac{m}{a_i} \rfloor\) 且 \(\gcd(p,q) = 1\) 的 \(q\) 的个数，容斥即可。

时间复杂度 \(O(n \sqrt m)\)。

code 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
#define pb emplace_back
int n, m, a[N];
int calc(int x, int lim) {
    vector <int> p;
    int rb = __builtin_sqrt(x);
    for (int i = 2; i <= rb; i++) {
        if (x % i) 
            continue;
        p.pb(i);
        while (x % i == 0)  
            x /= i;
    }
    if (x > 1)
        p.pb(x);
    int v = p.size();
    int ans = 0;
    for (int S = 0; S < (1 << v); S++) {
        int cur = 1;
        for (int i = 0; i < v; i++)
            if (S & (1 << i))
                cur *= p[i];
        if (__builtin_popcount(S) & 1) {
            ans -= (lim / cur);
        } else {
            ans += (lim / cur);
        }
    }
    return ans;
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i - 1] % a[i]) {
            cout << 0 << "\n";
            return;
        }
        int x = a[i - 1] / a[i];
        int lim = m / a[i];
        ans = 1ll * ans * calc(x, lim) % mod;
    }
    cout << ans << endl;
}
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
    return 0;   
}

E. Bracket Cost

给定一个长度为 \(n\) 的括号序列。你可以做以下操作：

  • 选择一个子串，将其循环右移一位。
  • 在括号序列的任意位置加一个左括号或右括号。

定义一个括号序列的代价为能将其变为匹配序列的最少操作次数，求这个括号序列所有的子串的代价之和。

\(n \leq 2 \times 10^5\)。

先无脑前缀和一下，考虑如何形式化地表示一个子串的代价。

对于一个括号序列，设 \(x,y\) 分别为失配的左、右括号数量，则最少操作次数为 \(\max(x,y)\)。这是因为删掉匹配的括号后，失配的括号形如 ))))((((，进行 \(\min(x,y)\) 次右移再补上 \(|x-y|\) 个括号即可。

记前缀和为 \(s\)。对于子串 \([l,r]\)，找到 \(s_x = \min \limits_{i = l-1}^r \{ s_i \}\)，那么前缀会有 \(-(s_x – s_{l-1})\) 个 ) 失配，后缀会有 \(s_r-s_x\) 个 ( 失配。因此答案即为：

\[\begin{aligned} c &= \sum_{i=1}^n \sum_{j=i}^n \max \left( s_{l-1} – \min_{k=i-1}^j \{ s_k \},s_r – \min_{k=i-1}^j \{ s_k \}\right) \\ &= \sum_{i=1}^n \sum_{j=i}^n \max(s_{l-1},s_r) – \min_{k=i-1}^j \{ s_k \} \\ &= \sum_{i=0}^{n-1} \sum_{j=i + 1}^n \max(s_i,s_j) – \min_{k=i}^j \{ s_k \} \end{aligned} \]

考虑 \(s_i\) 的贡献，第一项容易计算，第二项单调栈即可。时间复杂度 \(O(n \log n)\)。

code 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
int n, a[N];
int stk[N], tp, le[N], ri[N];
LL ans;
void solve() {
    string s;
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '(') {
            a[i] = a[i - 1] + 1;
        } else {
            a[i] = a[i - 1] - 1;
        }
    }
    tp = 0;
    for (int i = 0; i <= n; i++) {
        while (tp && a[i] < a[stk[tp]])
            tp--;
        if (tp == 0) {
            le[i] = 0; 
        } else {
            le[i] = stk[tp] + 1;
        }
        stk[++tp] = i;
    }
    tp = 0;
    for (int i = n; i >= 0; i--) {
        while (tp && a[i] <= a[stk[tp]])
            tp--;
        if (tp == 0) {
            ri[i] = n;
        } else {
            ri[i] = stk[tp] - 1;
        }
        stk[++tp] = i;
    }
    ans = 0;
    for (int i = 0; i <= n; i++) {
        ans -= 1ll * (i - le[i] + 1) * (ri[i] - i + 1) * a[i];
        ans += a[i];
    }
    sort(a, a + n + 1);
    for (int i = 0; i <= n; i++)
        ans += 1ll * a[i] * i;
    cout << ans << "\n";
}
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
    return 0;   
}

F. Majority

定义一个 \(01\) 串 \(s\) 是好的，当且仅当 \(s\) 可以通过若干次以下操作变为全 \(1\) 串：

  • 选择一个区间 \([i,j]\) 满足 \(s_i=s_j=1\)，\(2 \sum \limits_{k=i}^j s_k\ge j-i+1\)。

  • 将 \(k\in[i,j]\) 的 \(s_k\) 全部改为 \(1\)。

给定 \(n\) 和 \(p\)，求有多少个长度为 \(n\) 的 \(01\) 串是好的，答案对 \(p\) 取模。

显然，一个 \(01\) 串合法的必要条件是 \(s_1 = s_n = 1\)，我们不妨直接钦定这两个位置为 \(1\)。

考虑容斥，为此我们需要建立合法串和不合法串之间的联系。一个套路的做法是找到不合法串 “无法操作” 的终态并分析其结构，然后将所有不合法状态映射到这些状态上。

在本题中，“无法操作” 的状态 \(s\) 是这样的：

\(s\) 可以被划分为 \(2p+1\) 段，奇数段全为 \(1\)，偶数段全为 \(0\)。并且每个偶数段的长度大于与其相邻的两个奇数段长度之和。

接下来考虑如何将不合法状态映射到一个终态。对于一个终态 \(s\) 而言，一个不合法状态 \(s’\) 能够对应到它当且仅当对于 \(s\) 的奇数段，\(s’\) 的那些段都能变为全 \(1\) 串。也就是说，我们要考虑的其实是原问题的一个子问题。

那么计数就很简单了。我们设 \(f,g\) 分别为合法串和不合法串的答案，先通过子问题的 \(f’\) 算出当前问题的 \(g\)，然后根据容斥关系就能够算出当前问题的 \(f\) 了。

具体来说，设 \(f_i\) 表示长为 \(i\) 的合法段的数量，\(g_{i,j}\) 表示当前的 \(2p+1\) 段长度和为 \(i\)，最后一段长度为 \(j\) 的方案数。根据容斥关系，我们有：\(f_i + \sum \limits_{j=1}^{i-1} g_{i,j} = 2^{n-2}\)。

然后考虑如何递推出 \(g\)，根据定义，我们枚举倒数第二段和倒数第三段的长度，则有：

\[g_{i,j} = f_j \sum_{x=1}^i \sum_{k=1}^{\min(i-x,x-j-1)} g_{i-j-x,k} \]

由于定义域外的值一定都是 \(0\)，那么原式相当于 \(g_{i,j} = f_j \sum \limits_x \sum \limits_k [j + k < x] g_{i-j-x,k}\)。

令 \(p = i – j – x\)，那么条件即为 \(p+k \leq i – 2j – 1\)，即 \(g_{i,j} = f_j \sum \limits_{p+k \leq i – 2j – 1} g_{p,k}\)。

容易利用前缀和优化至 \(O(n^2)\)，然后就做完了。

code 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, mod, f[N], g[N][N], s[N], h[N][N];
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> mod;
    f[1] = s[1] = 1;
    int p = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = p;
        for (int j = 1; j <= i; j++) {
            if (i - 2 * j - 2 >= 1) {
                g[i][j] = 1ll * f[j] * s[i - 2 * j - 2] % mod;
            }
            f[i] = (f[i] + mod - g[i][j]) % mod; 
        }
        g[i][i] = f[i];
        for (int j = 1; j <= i; j++) {
            h[i][j] = (h[i - 1][j + 1] + g[i][j]) % mod;
        }
        s[i] = (s[i - 1] + h[i][1]) % mod;
        p = 1ll * p * 2 % mod;
    }
    cout << f[n] << "\n";
    return 0;   
}

G. Doping

定义排列 \(a\) 的权值 \(f(a)\) 为 \(a\) 最少可以划分成多少个区间，使得每个区间都是公差为 \(1\) 的等差数列。

给定长度为 \(n\) 的排列 \(p\)，对于 \(k=1,2,\cdots,n\) 求出，有多少个长度为 \(n\) 的排列 \(p’\)，满足 \(p’\) 字典序比 \(p\) 小，且 \(f(p’)=k\)，答案对 \(P\) 取模。

\(n \leq 2 \times 10^3\)。

考虑容斥，设 \(f_i\) 表示恰好能被分为 \(i\) 段的排列数量，\(g_i\) 表示钦定分为 \(i\) 段，但不要求相邻两端接口处的差 \(>1\) 的排列数量。那么有：\(g_i = \sum \limits_{j=1}^i \dbinom{n-j}{j-i} f_i\)。

其意义为恰好被分成 \(j\) 个段的排列还有 \(n-j\) 个位置可以切开，需要从中选择 \(i-j\) 个位置。

要求字典序小于 \(p\)，考虑枚举 LCP 之后计算。假设我们现在确定了一个长为 \(i-1\) 的 LCP，第 \(i\) 位需要填一个小于 \(p_i\) 的数。考虑将 \(p_{i\dots n}\) 分为 \(<p_i\) 和 \(\ge p_i\) 两类，设两类数中分别有 \(a_1,a_2\) 个差为 \(1\) 的数对，同时在值域上分别形成了 \(b_1,b_2\) 个连续段。

枚举 \(p’_{i\dots n}\) 被分成了 \(k\) 段 (\(b_1+b_2 \leq k \leq b_1+b_2+a_1+a_2\))，那么方案数为：

\[\sum_{j=0}^k \frac{b_1 + j}{k} k! \binom{a_1}{j} \binom{a_2}{k – b_1 – b_2 – j} \]

简单解释一下含义：我们枚举小于 \(p_i\) 的数多构成了多少个连续段，那么后面不小于 \(p_i\) 的数多构成的连续段数也随之确定了。由于要求 \(p’_i < p_i\)，因此在所有 \(k!\) 种连续段的排列方式中恰有 \(\dfrac{b_1 + j}{k}\) 是合法的。

利用 \(m \dbinom{n}{m} = n \dbinom{n-1}{m-1}\) 和范德蒙德卷积可以得到上式等于

\[b_1(k-1)!\binom{a_1+a_2}{k-b_1-b_2} + a_1(k-1)! \binom{a_1 + a_2 – 1}{k-b_1 – b_2 – 1} \]

当然还有特殊情况，即 \(p_i = p_{i-1}+1\)，此时可以选择不钦定 \(i\) 作为一段的起点，这样的方案数为 \(\dfrac{k!}{k}\dbinom{a_1+a_2}{k-b_1-b_2}\)。这是因为在这种情况下 \(p_{i-1}+1\) 一定是一个连续段的起点，可以不枚举。而补满缺少的 \(k-b_1-b_2\) 个钦定的连续段之后的所有连续段排列有 $\dfrac{1}{k} $ 满足条件。

但如果对每个 \(i\) 都进行容斥复杂度就会达到 \(O(n^3)\)，我们希望只在最后进行一次容斥。考虑 DP，设 \(g_{i,j}\) 表示只考虑 \(p_{i\dots n}\) 时 \(g_j\) 的值。转移比较简单，如果 \(p_i-1=p_{i-1}\) 就可以选择是否钦定分段，那么有 \(g_{i,j}=g_{i,j-1}+g_{i,j}\)。否则一定要分段，即 \(g_{i,j}=g_{i,j-1}\)。

只需要在 \(g_{i,j}\) 处加入 \(p_{i\dots n}\) 钦定被分为 \(j\) 段的方案数，然后往前推即可。时间复杂度 \(O(n^2)\)。

code 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, mod, a[N], f[N], g[N];
int fac[N], C[N][N]; 
bool vis[N];
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> mod;
    for (int i = 1; i <= n; i++)    
        cin >> a[i];
    C[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
    }
    for (int i = n; i >= 1; i--) {
        if (i > 1 && a[i - 1] == a[i] - 1) {
            for (int j = n - 1; j >= 0; j--) 
                f[j + 1] = (f[j + 1] + f[j]) % mod;
        } else {
            for (int j = n - 1; j >= 0; j--)
                f[j + 1] = f[j];
            f[0] = 0;
        }
        vis[a[i]] = true;
        int a1 = 0, b1 = 0;
        int a2 = 0, b2 = 0;
        for (int j = 1; j < a[i]; j++) {
            if (!vis[j])
                continue;
            if (vis[j - 1]) { 
                b1++;
            } else {
                a1++;
            }
        }
        for (int j = a[i]; j <= n; j++) {
            if (!vis[j])
                continue;
            if (vis[j - 1]) {
                b2++;
            } else {
                a2++;
            }
        }
        int A = a1 + a2;
        int B = b1 + b2;
        for (int j = A; j <= A + B; j++) {
            f[j] = (f[j] + 1ll * fac[j - 1] * a1 % mod * C[B][j - A] % mod) % mod;
            if (j > A) {
                f[j] = (f[j] + 1ll * fac[j - 1] * b1 % mod * C[B - 1][j - A - 1] % mod) % mod;
            } 
            if (i > 1 && vis[a[i - 1] + 1] && a[i - 1] + 1 < a[i]) {
                f[j - 1] = (f[j - 1] + 1ll * fac[j - 1] * C[B][j - A] % mod) % mod;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        g[i] = f[i];
        for (int j = 1; j < i; j++) {
            g[i] = (g[i] + mod - 1ll * g[j] * C[n - j][i - j] % mod) % mod;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << g[i] << " ";
    cout << "\n";
    return 0;   
}

H. BinaryStringForces

NOIp 后再补吧

原文地址：http://www.cnblogs.com/came11ia/p/16919478.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性