2024 牛客多校 01

C - Sum of Suffix Sums

题目描述

给定一个初始为空的数组，您需要执行 \(q\) 次操作：

每次操作，给出非负整数 \(t\) 和 \(v\)，取出数组末尾的 \(t\) 个元素，然后再将 \(v\) 插入到数组末尾，保证操作时 \(t\) 不会超过数组的长度。

对于每次操作，输出数组中所有元素的 后缀和之和 对 \(10^9 + 7\) 取模的结果。

即，令 \(S_i = \sum_{j = i}^{n} a_j\)，对于每次操作，输出 \(\sum_{i = 1}^{n} S_i \mod (10^9 + 7)\)。

输入

第一行输入一个数 \(q\)，表示操作次数 \(1 \leq q \leq 10^5\)。 接下来 \(q\) 行，每行输入两个数 \(t\) 和 \(v\)，表示一次操作 \(0 \leq v \leq 10^9\)，对于 \(t\)，保证操作时 \(t\) 不会超过数组的长度。

输出

输出 \(q\) 行，每行输出一个数，表示每次操作后的结果。

---

题解

比较简单的签到，对于每个被加在数组末尾的元素 \(a_i\)，它对答案的贡献可以 \(O(1)\) 计算出，为 \(a_i *i\)，无论将这个元素添加或删除，贡献的计算都可以 \(O(1)\) 完成；同时，每次询问最多添加一个元素，而删除元素时保证非空，因此可以确定时间复杂度是 \(O(q) 的\)

由于涉及到取模，因此还有快速幂求乘法逆元，同时，我在这题强化了自己减法取模的技巧。

AC 代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;

int fastpow(int a, int k) {
  int res = 1;
  while (k) {
    if (k & 1) {
      res = (res * a) % mod;
    }
    a = (a * a) % mod;
    k >>= 1;
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int q;
  cin >> q;

  vector<int> a;
  int ans = 0;

  while (q--) {
    int t, x;
    cin >> t >> x;

    for (int i = 0; i < t; i++) {
      ans = ((ans - (int)a.size() * a.back()) % mod + mod) % mod;
      a.pop_back();
    }

    a.push_back(x);
    ans = (ans + (int)a.size() * a.back()) % mod;
    cout << ans << '\n';
  }
}

H - World Finals

题目描述

有两场 World Finals 同时举办，每场都有若干出线队伍，两场出线名单可能有重复的队伍，而一个队伍只能选择其中的一场参加，然后每场比赛的每支队伍都有一个预测成绩（过题数 + 罚时）。

lzr010506 在两场 World Finals 都出线了，他想知道如果所有队伍的最终成绩就是预测成绩，对于所有同时在两场 World Finals 出线的队伍，他能自由操纵队伍参加哪一场。问他能取得的最好名次是什么。

输入

第一行输入一个数 \(n\)，表示出线 46th World Finals 的队伍数 \(1 \leq n \leq 10^5\)。 接下来 \(n\) 行，每行输入字符串 S（\(|S| \leq 10\)）和两个数 \(p, t\)，表示队伍名字和预测成绩（过题数 + 罚时数）\(1 \leq p, t \leq 10^9\)。

接下来输入一个数 \(m\)，表示出线 47th World Finals 的队伍数 \(1 \leq m \leq 10^5\)，接下来的格式和上面一样。

输出

输出一个数，表示 lzr010506 能取得的最好名次。

---

题解

感觉是比上一题更签的签到，但是码了一通上去 T 了。

思路上很容易想到，如果 lzr010506 参加 46th，那就尽量把所有人赶去参加 47th，反之亦然；为了找出两次比赛中重叠的队伍，可以用 map、set 之类的数据结构。

剩下就是一个简单的结构体排序了。

我第一发 T 的原因是，我只用 vector 存了队伍名字，排序的时候按照队伍名字去 map 里找对应的成绩，平白无故在排序的每次比较中多了 \(O(|S|\log n)\) 的复杂度，最后结果应该是 \(O(|S|n ({\log n}) ^ 2 )\) 的，恰好被极限数据卡到 \(10^9\) 的数量级。

AC 代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;
const int inf = 2e9;

struct uni{
  string name;
  int num, time;
  bool operator<(const uni& other) {
    if (num == other.num) {
      return time < other.time;
    }
    return num > other.num;
  }
};

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  set<string> count;
  set<string> repeat;

  vector<uni> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].name >> a[i].num >> a[i].time;
    count.insert(a[i].name);
  }

  int m;
  cin >> m;
  vector<uni> b(m);
  for (int i = 0; i < m; i++) {
    cin >> b[i].name >> b[i].num >> b[i].time;
    if (count.count(b[i].name)) {
      repeat.insert(b[i].name);
    }
  }


  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  int ans = inf;
  int remove = 0;

  for (int i = 0; i < n; i++) {
    if (a[i].name == "lzr010506") {
      ans = min(ans, i + 1 - remove);
    }
    remove += repeat.count(a[i].name);
  }

  remove = 0;
  for (int i = 0; i < m; i++) {
    if (b[i].name == "lzr010506") {
      ans = min(ans, i + 1 - remove);
    }
    remove += repeat.count(b[i].name);
  }

  cout << ans << '\n';
}

A - A bit Common

题目描述

给定两个整数 \(n\) 和 \(m\)，在所有包含 \(n\) 个非负整数且每个整数都小于 \(2 ^ m\) 的所有序列中，需要统计这样的序列的数量：这种序列使得存在一个非空子序列，其中整数的按位与结果恰好为 1。

输出答案对 \(p\) 取模的结果。

输入

三个整数 \(n, m, p\)，表示序列长度，整数范围和模数 \(1 \leq n, m \leq 10^5, 1 \leq 10^9\)。

输出

输出一个数，表示答案对 \(p\) 取模的结果。

---

题解

一道难度不高的组合数学题。

一个序列的某个子序列按位与为 1，那么这个序列所有末位是 1 的数按位与结果一定是 1. 我们考虑分类讨论有多少个末尾是 1 的数，分别有多少种可能的方式用这些数构造出一个按位与为 1 的子序列。

选取 \(i\) 个末尾是 1 的数在序列中的位置，有 \(C(n, i)\) 种可能，对于剩余的 \(m - 1\) 位，我们可以随意取值，但是必须保证每个位置上至少有一个数是 0，也就是排除全 0 的情况，有 \(2^{m - 1} - 1\) 种可能。

即，对于每个 \(i\)，末尾是 1 的数有 \(C(n, i) * (2^{m - 1} - 1)\) 种可能，最后答案是所有 \(i\) 的可能性之和。

然后剩下的 \(n - i\) 个数的末位是 0，那么这 \(n - i\) 个数的前 \(m - 1\) 位可以随意取值，有 \({2^{m - 1}} ^ {n - i}\) 种可能。

这里同时涉及到两个问题，一个是要计算快速幂，另一个是要计算组合数。

我们队在计算组合数的时候被卡了很久，因为这里的模数是每一轮输入的，因此无法通过预处理阶乘和逆元的方式来计算组合数，而是要在计算组合数的时候直接取模。

好在这道题的数据范围不大，因此可以使用 \(O(n ^ 2)\) 的杨辉三角递推式来计算组合数。

AC 代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e3 + 10;

int memo[N][N];
int mod;

void init() {
  for (int i = 1; i < N; i++) {
    memo[1][i] = i % mod;
  }
  for (int i = 2; i < N; i++) {
    for (int j = i; j < N; j++) {
      memo[i][j] = (memo[i - 1][j - 1] + memo[i][j - 1]) % mod;
    }
  }
}

int C(int up, int down) {
  if (up > down) {
    return 0;
  }
  return memo[up][down] % mod;
}

int fastpow(int a, int k) {
  int res = 1;
  while (k) {
    if (k & 1) {
      res = (res * a) % mod;
    }
    a = (a * a) % mod;
    k >>= 1;
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m >> mod;

  init();

  int ans = 0;
  for (int i = 1; i <= n; i++) {
      ans += C(i, n) * fastpow(fastpow(2, m - 1), n - i) % mod * fastpow(fastpow(2, i) - 1, m - 1) % mod;
      ans %= mod;  
  }
  cout << ans << '\n';
}

B - A bit More Common

题目描述

在上一题的基础上，现在的要求是，序列中至少有两个子序列能保证按位与结果为 1，求答案对 \(p\) 取模的结果。