首页 > 其他分享 >AtCoder Beginner Contest 293 补题记录 (E-G)

AtCoder Beginner Contest 293 补题记录 (E-G)

时间：2023-04-15 17:00:41浏览次数：57  
标签：tmp AtCoder return Beginner int LL long ++ 补题

E

题意：给定 A, X, M, 计算 (A0 + A1 + A2 + ... + AX-1) mod M (1 <= A, M <= 109, 1 <= X <= 1012)。

 

根据等比数列求和公式，(A0 + A1 + A2 + ... + AX-1) mod M = ((AX - 1) / (A - 1)) mod M。然而，此题如果用求和公式来求解显然是行不通的，下面会给出原因。

 

如果我们要用求和公式求解此题，首先，我们不能直接计算 ((AX - 1) mod M) / ((A - 1) mod M) mod M，因为对于正整数 a, b, p, "(a + b) mod p = ((a mod p) + (b mod p)) mod p" 这个等式是恒成立的，把 '+' 换成 '-' 或 '*' 也仍然恒成立，但如果是 '/'，"恒成立" 这个说法就是错的。所以，对于取模运算下的除法，我们要想办法将其转化为乘法，我们需要找出一个正整数 x，使得在 mod p 的前提下，除以 b 就相当于乘以 x，即 (a / b) mod p = (a * x) mod p,  这个 x 称为 "b 在模 p 下的乘法逆元"，记为 b-1(mod p)。b, x 满足 (b * x) mod p = 1 (这和 "倒数" 的概念可以说非常相似)。

求解方程 (b * x) mod p = 1，实际上就是要求出不定方程 bx + py = 1 的一组特解。根据贝祖定理，当且仅当 b, p 互质时才存在整数解。很遗憾，此题数据无法保证 (A - 1) 和 M 互质，所以用求和公式不可行。

解法一：举个例子，如果我们要计算 A0 + A1 + A2 + ... + A7，我们可以把它看成 (A0 + A1 + A2 + A3)、(A4 + A5 + A6 + A7) 之和，这二者又成倍数关系，所以原式就等于 (1 + A4) * (A0 + A1 + A2 + A3)。(1 + A4) 可以用快速幂计算得出，而 (A0 + A1 + A2 + A3) 又可以继续划分。如果原式最后一项不是 A7 而是 A8 ，项数是奇数怎么办？用快速幂单独计算 A8 再加上即可。这样一来，我们就得到了一个不断将原式一分为二的递归分治算法，时间复杂度为 O(logX)。

代码 (太菜了 20 多分钟才调出来 o(TヘTo) )：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

LL ebs(const LL &a, const LL &b, const LL &m) {              // 快速幂, 计算 (a ^ b) mod p
  if (b == 0) return 1 % m;
  LL tmp = ebs(a, b >> 1, m);
  if (b & 1) return (tmp * tmp % m * a % m);
  else return (tmp * tmp % m);
}

LL calc(const LL &a, const LL &x, const LL &m) {             // 计算 a ^ 0 + a ^ 1 + ... + a ^ (x - 1)
  if (x == 1) return 1 % m;                                  // 递归边界, x == 1 表示只有一项, 无法继续划分
  LL tmp = (1 + ebs(a, x >> 1, m)) * calc(a, x >> 1, m) % m;
  if (x & 1) return ((tmp + ebs(a, x - 1, m)) % m);          // 若 x 为奇数则单独计算 a ^ (x - 1), 再把它加上
  else return tmp;
}

int main(void) {
  LL a, x, m;
  cin >> a >> x >> m;
  cout << calc(a, x, m) << '\n';
  return 0;
}

 

这里的的 "快速幂" 是递归实现的，实际上非递归也可以，如下：

long long pow_mod(long long a, long long b, long long p) {
  assert(p != 0);
  long long res = 1 % p;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
  }
  return res;
}

 

解法二：矩阵乘法加速递推

看了官方题解才知道这题还可以用矩阵，感觉上面那个解法明显更容易想到。时间复杂度同样为 O(logX)。

其中 Bi = A0 + A1 + ... + Ai,  不妨令 B0 = 0，显然 Bi = Bi-1 * A + 1。Bx 即为所求的答案。初始化矩阵 state = (B0, 1), 用 "矩阵快速幂" 计算出上式中 2 * 2 矩阵的 X 次方，再令 state 右乘之，即可得出答案。

 

代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
  LL a, x, m;
  cin >> a >> x >> m;

  LL state[1][2] = {{0, 1}};         // 状态矩阵 state
  LL trans[2][2] = {{a, 0}, {1, 1}}; // 转移矩阵 trans
  LL mat[2][2] = {{1, 0}, {0, 1}};   // 矩阵 mat 用来参与计算 trans 的 x 次方, 先初始化为单位矩阵

  LL tmp[2][2] = {{0, 0}, {0, 0}};   // 矩阵 tmp 用于临时保存每次进行矩阵乘法的结果
  auto clear_tmp = [&]() -> void {   // 该 lambda 表达式用于将 tmp 归零
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) tmp[i][j] = 0;
    return;
  };

  for (; x; x >>= 1) {
    if (x & 1) {
      // 令 mat 乘上 trans
      clear_tmp();
      for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
          for (int k = 0; k < 2; ++k) tmp[i][j] = (mat[i][k] * trans[k][j] % m + tmp[i][j]) % m;
      for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j) mat[i][j] = tmp[i][j];
    }
    // 令 trans 自乘
    clear_tmp();
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k) tmp[i][j] = (trans[i][k] * trans[k][j] % m + tmp[i][j]) % m;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) trans[i][j] = tmp[i][j];
  }

  // 最后一步, 令 state 乘上 mat
  clear_tmp();
  for (int i = 0; i < 1; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k) tmp[i][j] = (state[i][k] * mat[k][j] % m + tmp[i][j]) % m;
  state[0][0] = tmp[0][0], state[0][1] = tmp[0][1];

  cout << state[0][0] << '\n';

  return 0;
}

 

F

题意：给定正整数 N，计算有多少个不小于 2 的正整数 b，使得 N 在 b 进制下每一位均为 0 或 1。输出满足条件的 b 的个数。有 T 组测试数据。(1 <= T <= 1000, 1 <= N <= 1018)

解法：这题对我来说思维难度挺高的，比赛的时候完全没有思路。看了下官方题解才知道这道题有一个关键点：当 b > 1000 时，N 在 b 进制下不会超过 6 位数。所以我们可以先枚举 2~1000 看有多少个能满足条件。然后开一个 6 个元素的数组，每一个元素都只取 0 或 1 这两个值，就总共有 26 = 64 种情况。对于每一种情况，我们判断是否存在一个 b，使得 N 的 b 进制下的表示与这个数组表示的数完全相等，这个过程可以用二分查找来完成 (即可以查找最大的 b，使得 N 的 b 进制数大于等于该数组表示的数，然后判断是否能取等号)。

时间复杂度：O(T(999 + 64logN))

代码： 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

bool trial(LL n, LL base) {                // 该函数用于判断 n 在 base 进制下是否全为 0 或 1
  while (n) {
    if (n % base > 1) return false;
    n /= base;
  }
  return true;
}

vector<LL> generate(LL n, LL base) {       // 该函数用于生成 n 的 base 进制, 返回一个存储六个 long long 的 vector 对象
  vector<LL> ans(6, 0);
  for (int i = 5; i >= 0; --i) {
    ans[i] = n % base;
    n /= base;
  }
  return ans;
}

vector<LL> num;
void dfs(LL &ans, LL n, int step) {
  if (step == 6) {                         // 递归边界，此时我们已经得到了数组 num 的一种情况, 开始 "二分查找" 这一步骤
    LL l = 1001, r = n, mid = 0;
    while (l < r) {
      mid = (l + r + 1) >> 1;
      vector<LL> res = generate(n, mid);   // 数组 res 表示 N 的 mid 进制

      bool less = false;                   // 让数组 res 和 num 进行比较, 判断是 res < num 还是 res >= num
      for (int i = 0; i < 6; ++i) {
        if (res[i] < num[i]) {
          less = true;
          break;
        }
      }

      if (less) r = mid - 1;               // 如果 res < num, 说明 mid 大于我们要找的 b, b 一定在在 [l, mid - 1] 范围内
      else l = mid;                        // 如果 res >= num, 则 mid 小于等于我们要找的 b, b 一定在在 [mid, r] 范围内
    }
    vector<LL> res = generate(n, l);       // 此时的 l 即为我们要查找的最大的 b, 使得 N 的 b 进制数大于等于该数组表示的数

    bool equal = true;                     // 最后判断是否可以取等号
    for (int i = 0; i < 6; ++i) {
      if (res[i] != num[i]) {
        equal = false;
        break;
      }
    }
    if (equal) ++ans;
    return;
  }

  num[step] = 1;
  dfs(ans, n, step + 1);
  num[step] = 0;
  dfs(ans, n, step + 1);
  return;
}

void solve(void) {
  LL n, ans = 0;
  cin >> n;
  for (LL i = 2; i <= min(1000LL, n); ++i) // 枚举 2 ~ 1000
    if (trial(n, i)) ++ans;

  if (n > 1000) {
    num.assign(6, 0);                      // 先将数组 num 赋值为 6 个 0
    dfs(ans, n, 0);                        // 然后递归枚举每一种情况
  }

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

int main(void) {
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

 

G

题意：给定有 N 个元素的数组 A, Q 个询问, 每次询问指定一个区间 [l, r], 问在 Al, Al+1, ..., Ar 这 (r - l + 1) 个数中有多少个不同的三元组 (i, j, k) 满足 Ai = Aj = Ak。

解法：这道题是莫队算法的模板题，这个算法我刚接触不久，还不太懂它为什么能把时间复杂度降到 O(n√n) ( 还望大佬们能指点指点 ( •̀ ω •́ )✧ )。大概意思就是，这道题，如果我们已经知道了一个区间 [l, r] 的答案，那么对于[l+1,r], [l, r - 1], [l - 1, r], [l, r + 1] 这四个区间，我们也可以用 O(1) 的时间得出答案。定义两个变量 l, r 用于表示区间 [l, r] 的左右边界，如果我们已经知道了第 i 个询问，即 [li, ri] 的答案，那么对于下一个提问，只要一步一步地移动 l 和 r，直至 l = li+1, r = ri+1 就可以得出下一个提问的答案。用分块的思想对提问进行合理的排序，可以有效地降低时间复杂度。

代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int a[200005];
int st[500], en[500];
int bel[200005];

LL cnt[200005];
LL ans[200005], cur;

LL C3(const LL &n) {
  if (n < 3) return 0LL;
  return n * (n - 1) / 2LL * (n - 2) / 3LL;
}

void add(const int &p) {
  cur -= C3((LL)cnt[a[p]]);
  ++cnt[a[p]];
  cur += C3((LL)cnt[a[p]]);
  return;
}

void del(const int &p) {
  cur -= C3((LL)cnt[a[p]]);
  --cnt[a[p]];
  cur += C3((LL)cnt[a[p]]);
  return;
}

struct Query {
  int id;
  int l;
  int r;
  bool operator<(const Query &a) const {
    if (bel[l] != bel[a.l]) return l < a.l;
    return (bel[l] & 1) ? r < a.r : r > a.r;
  }
} q[200005];

int main(void) {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= m; ++i) {
    q[i].id = i;
    cin >> q[i].l >> q[i].r;
  }

  // 分块
  int sq = sqrt(n);
  for (int i = 1; i <= sq; ++i) {
    st[i] = sq * (i - 1) + 1;
    en[i] = sq * i;
  }
  if (en[sq] < n) {
    ++sq;
    st[sq] = en[sq - 1] + 1;
    en[sq] = n;
  }
  for (int i = 1; i <= sq; ++i) {
    for (int j = st[i]; j <= en[i]; ++j) bel[j] = i;
  }

  // 将询问进行排序
  sort(q + 1, q + m + 1);

  int l = q[1].l, r = q[1].r;
  for (int i = l; i <= r; ++i) add(i);
  ans[q[1].id] = cur;
  for (int i = 2; i <= m; ++i) {
    while (l > q[i].l) add(--l);
    while (r < q[i].r) add(++r);
    while (l < q[i].l) del(l++);
    while (r > q[i].r) del(r--);
    ans[q[i].id] = cur;
  }
  for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';

  return 0;
}

有不足的地方欢迎指出啊 (。・∀・)ノ

 

标签：tmp,AtCoder,return,Beginner,int,LL,long,++,补题
From： https://www.cnblogs.com/xbai2/p/17320891.html

相关文章

  • AtCoder Regular Contest 104 D Multiset Mean
    洛谷传送门AtCoder传送门很平凡的一道计数啊。考虑将所有数都减去\(x\)，那么就要求选的数和为\(0\)。正负分开考虑，\(0\)可以任意选。需要多重背包求\(f_{i,j}\)表示选\(1\simi\)的数和为\(j\)的方案数。前缀和优化是平凡的。code//Problem:D-MultisetMean......
  • AtCoder Beginner Contest 297
    A-DoubleClick#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongint32_tmain(){intn,d;cin>>n>>d;vector<int>a(n);for(auto&i:a)cin>>i;for(inti=1;i<......
  • AtCoder Beginner Contest 207（D,E)
    AtCoderBeginnerContest207（D,E)D(计算几何)D这个题是两个点的集合，每个集合有\(n\)个点，我们可以让一个集合中的每一个点进行下面两种操作\(1\),可以让每一个点进行旋转\(x\)的角度\(2\),可以让每一个点的\(x\)变成\(x+disx\),\(y\)变成了\(y+disy\)问是否可以让这两个集合......
  • AtCoder Beginner Contest 247（E,F)
    AtCoderBeginnerContest247（E,F)E(思维)E这个题大意就是给一个长度为\(n\)的数组，一个\(x\)和一个\(y\),问这个数组里面可以找到多少段\([l,r]\)满足这一段里面的最大值是\(x\)，最小值是\(y\)这里的做法是固定最右端，寻找最左端的可能的数量，最后相加对于每一个位置，都有作为最......
  • AtCoder Regular Contest 127
    D-LIS2难搞的地方在于取min，考虑比较\((a_i\oplusa_j,b_i\oplusb_j)\)两者的过程：是在它们第一位不一样的地方比较，取该位为0的那个。而判断两个数在某位是否相等，可以想到异或操作，然后把这两者异或起来后，由异或运算的交换律可得等价于\((a_i\oplusb_i)\oplus(a_j\oplus......
  • AtCoder Regular Contest 159
    Preface这周六紧张刺激的一日三赛，上午蓝桥杯，晚上ARC之后隔5min就是CF，可谓是手搓键盘到冒烟的一天了这场其实打的感觉很没水准，B刚开始没想清楚很多边界条件挂了三发，45min左右才过然后C的构造也不太会，随便写了个暴力也是挂挂挂，只好弃了去写D题了结果发现D题好像是个不难的线段树......
  • 练习记录- AtCoder Beginner Contest 295（D）
    vp的觉得我的D很聪明所以来写一下（乐D-ThreeDaysAgo题意就是求所有字符出现次数均为偶数的字串数量太笨了所以想了很久我把存在奇数个1当作第2位是2那么当经过了两次1 2^2这个2就变成了02就是第二位就是4...以此类推 所以我遍历一遍字符串求出当前的异或......
  • 练习记录-AtCoder Beginner Contest 296(A-F)
    vp的感觉整场挺智慧A-Alternately找有没有连续的男女#include<bits/stdc++.h>#defineclosestd::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)usingnamespacestd;typedeflonglongll;constllMAXN=3e5+7;constllmod=1e9+7;constllinf=0x3......
  • AtCoder Beginner Contest 278
    口胡一下，从青色开始E-GridFilling给定一个W×H的矩阵，每个格子有一个数，在1和N之间，给定w<=W，h<=H,对于每个满足1<=i<=W-w+1,1<=j<=H-h+1的格子(i,j)，求以它为左上角的w×h矩阵被遮住后整个大矩阵还剩下几种数字。W,H,N,w,h<=300首先我们看见这个熟悉的300就知道是立方算法又注......
  • AtCoder ABC286 C - Chinese Restaurant
    AtCoderABC286C-ChineseRestaurant题目描述有\(N\)个人从\(0\)开始编号，按逆时针顺序间隔均匀地坐在转盘周围。在开始时，第\(p_i\)盘菜在第\(i\)个人的前面。现在，你可以进行以下操作\(0\)次或多次。将转盘逆时针旋转\(\dfrac{1}{N}\)圈。也就是说，旋转前......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99