出生于驾校 - 题目 - AlgoBeat OnlineJudge

内存限制：2048 MiB 时间限制：2500 ms 标准输入输出

题目类型：VJudge（洛谷）评测方式：VJudge

上传者：匿名

提交提交记录统计讨论题解

扶苏有一个长度为的数列。您要帮她支持如下操作，共次：

1 x：给数列里每个数都加上，即对，都执行，其中表示赋值。
2 x：给数列里每个数都乘上，即对，都执行，其中表示赋值。
3 k p：对所有满足的，求的和对取模的结果，即求，其中是艾佛森括号。

为了避免输出过大，你只需要输出所有操作的结果的按位异或和。

本题的输入规模非常巨大，因此我们提供了一个随机数生成器来生成数列和询问。你可以参考输入格式来具体查阅内容。

为了避免读入过大，我们将提供如下数据生成器：

标准输入共两行，第一行有四个整数。其中和表示数列长度和操作次数，和表示输入的最小和最大值。数据生成器将用到这两个数值。

我们提供了 C++、Java、Python 三种语言的数据生成器参考代码，你可以在说明/提示中直接参考和使用这些代码，而无需被担心判定为作弊。

标准输入第二行有三个参数，这三个参数是 32 位无符号整型，数据生成器将利用这三个参数生成随机数。

你应该定义如下函数：

typedef uint32_t ui;
ui X, Y, Z;

ui nextInt(ui &x = X, ui &y = Y, ui &z = Z) {
  x ^= y << (z & 31);
  y ^= z >> (x & 31);
  z ^= x << (y & 31);
  x ^= x >> 5; y ^= y << 17; z ^= z >> 6;
  return x;
}

接下来，每次调用 nextInt() 函数，你都将得到一个位无符号整数。

读入标准输入里的两行个整数后，你已经得到了和的值，接下来按如下代码生成数列：

const int lim = 998'244'353;
std::vector<int> genArr(int n) {
  std::vector<int> ret(n);
  for (int i = 0; i < n; ++i) ret[i] = nextInt() % lim;
  return ret;
}

接下来，你要生成次操作，对每次操作，方法如下：

令 op = nextInt() % 3 + 1
若或，取 x = nextInt() % lim
否则依次取：k = nextInt() % (maxK - minK + 1) + minK, p = nextInt() % (1 << k)

这样，你就能拿到每次操作的信息了。

输出一行一个整数，表示所有操作的结果的按位异或和。

样例输入 1

5 7 0 2
1 2 3

样例输出 1

89001694

样例解释

调用数据生成器得到的序列；

得到的操作依次是：

2 558452929
2 832199221
1 38834385
3 0 0
3 1 1
1 818308198
2 135235876

数据规模与约定

测试点编号			特殊约定
			无



			无

对全部的测试数据，保证，，，，。

为了帮助你快速判断当前测试点的特殊约定，我们保证：编号为的测试点所读入的的末位数字为。

参考实现

【C++ 参考实现】

#include <bits/stdc++.h>

typedef uint32_t ui;
int n, q, minK, maxK;
ui X, Y, Z;

ui nextInt(ui &x = X, ui &y = Y, ui &z = Z) {
  x ^= y << (z & 31);
  y ^= z >> (x & 31);
  z ^= x << (y & 31);
  x ^= x >> 5; y ^= y << 17; z ^= z >> 6;
  return x;
}

const int lim = 998'244'353;
std::vector<int> genArr(int n) {
  std::vector<int> ret(n);
  for (int i = 0; i < n; ++i) ret[i] = nextInt() % lim;
  return ret;
}

int main() {
  std::cin >> n >> q >> minK >> maxK;
  std::cin >> X >> Y >> Z;
  std::vector<int> a = genArr(n);
  for (int _ = 1; _ <= q; ++_) {
    int op = nextInt() % 3 + 1;
    if (op == 1) {
      int x = nextInt() % lim;
      //fill your code here
    } else if (op == 2) {
      int x = nextInt() % lim;
      //fill your code here
    } else {
      int k = nextInt() % (maxK - minK + 1) + minK;
      int p = nextInt() % (1 << k);
      //fill your code here
    }
  }
  //fill your code here
}

【Java 参考实现】

import java.util.Scanner;

public class Main {
  private static final int lim = 998244353;
  private static long X, Y, Z;

  private static long maskToU32(long x) {
    return x & 0xFFFFFFFFL;
  }

  private static long nextInt() {
    long x = X;
    long y = Y;
    long z = Z;

    x ^= y << (z & 31);
    x = maskToU32(x);
    y ^= z >>> (x & 31);
    y = maskToU32(y);
    z ^= x << (y & 31);
    z = maskToU32(z);

    x ^= x >>> 5;
    x = maskToU32(x);
    y ^= y << 17;
    y = maskToU32(y);
    z ^= z >>> 6;
    z = maskToU32(z);

    X = x;
    Y = y;
    Z = z;

    return X;
  }

  private static int[] genArr(int n) {
    int[] ret = new int[n];
    for (int i = 0; i < n; ++i) {
      ret[i] = (int)(nextInt() % lim);
    }
    return ret;
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int q = scanner.nextInt();
    int minK = scanner.nextInt();
    int maxK = scanner.nextInt();
    X = scanner.nextLong();
    Y = scanner.nextLong();
    Z = scanner.nextLong();

    int[] a = genArr(n);

    for (int qId = 1; qId <= q; qId++) {
      long op = nextInt() % 3 + 1;
      if (op == 1) {
        int x = (int)(nextInt() % lim);
        // fill your code here
      } else if (op == 2) {
        int x = (int)(nextInt() % lim);
        // fill your code here
      } else {
        int k = (int)(nextInt() % (maxK - minK + 1) + minK);
        int p = (int)(nextInt() % (1 << k));
        // fill your code here
      }
    }
    // fill your code here
  }
}

【Python 参考实现】

X = 0
Y = 0
Z = 0

lim = 998244353


def nextInt():
  global X, Y, Z
  x = X
  y = Y
  z = Z

  x ^= (y << (z & 31)) & 0xFFFFFFFF
  x &= 0xFFFFFFFF

  y ^= (z >> (x & 31)) & 0xFFFFFFFF
  y &= 0xFFFFFFFF

  z ^= (x << (y & 31)) & 0xFFFFFFFF
  z &= 0xFFFFFFFF

  x ^= (x >> 5)
  x &= 0xFFFFFFFF

  y ^= (y << 17) & 0xFFFFFFFF
  y &= 0xFFFFFFFF

  z ^= (z >> 6)
  z &= 0xFFFFFFFF

  X, Y, Z = x, y, z
  return X


n, q, minK, maxK = map(int, input().split())
X, Y, Z = map(int, input().split())

a = [nextInt() % lim for _ in range(n)]

for _ in range(q):
  op = nextInt() % 3 + 1
  if op == 1:
    x = nextInt() % lim
    #fill your code here
  elif op == 2:
    x = nextInt() % lim
    #fill your code here
  elif op == 3:
    k = nextInt() % (maxK - minK + 1) + minK
    p = nextInt() % (1 << k)
    #fill your code here

#fill your code here

编辑器加载中 …

或者，上传代码文件

#212594. 出生于驾校

题目描述

输入格式

输出格式

样例

样例输入 1

样例输出 1

数据范围与提示

样例解释

数据规模与约定

参考实现

显示分类标签