#C. 第 8 号女王蜂生产工厂

    传统题 1500ms 256MiB

第 8 号女王蜂生产工厂

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Snipaste2023-08-0720-25-01.png

题目描述

在这个题目中,你需要解决这样一个问题:

给定一个长度为 www=60w=60)的 0101 序列 a0,1,2,w1a_{0,1,2\dots,w-1},你需要求出他有多少个子区间的区间和等于区间长度。

为了压缩读入量,序列 aa 将采用特殊的方法生成,具体的,你将读入一个正整数 xxx<2wx< 2^{w}) 表示 aa,其中 $x=a_0\times 2^{0}+a_1\times 2^1\dots a_{w-1}\times 2^{w-1}$。

本题有多组询问,共 qqq5×107q\le 5\times 10^7) 次,将采用读入和随机相结合的方式生成,具体方法见输入格式。

输入格式

第一行四个正整数 q,k,a,cq,k,a,c,其中 qq 的含义见题目描述,k,a,ck,a,c 用以读入数据,具体方法如下:

该题所有 qq 次询问中,前 kk 次询问的 x1,x2,,xkx_1,x_2,\dots,x_k 在输入中给定,每行一个,从第 k+1k+1 次询问开始的 xi=(xorshift(xi1)+a)modcx_i=(\operatorname{xorshift}(x_{i-1})+a)\bmod c。其中 xorshift\operatorname{xorshift} 的具体含义将在下方以代码形式给出。

保证 c2wc\leq 2^w

xorshift\operatorname{xorshift} 代码片段如下:

unsigned long long xorshift(int X){
	X ^= X << 13; X ^= X >> 17; X ^= X << 5; return X;
}

读入模板,保证该读入模板耗时小于 600 ms\text{600 ms}

#include<bits/stdc++.h>
unsigned long long a, c, x;
int q, k;
namespace Read{
	int cnt = 0; unsigned long long X;
	unsigned long long read(){
		if(++ cnt <= k) {std :: cin >> X; return X;}
		else {X ^= X << 13; X ^= X >> 17; X ^= X << 5; return X = (X + a) % c;}
	}
}
int main(){
	std :: ios :: sync_with_stdio(false); std :: cin.tie(0);
	std :: cin >> q >> k >> a >> c; 
	for(int i = 1; i <= q; i ++){
		x = Read :: read();
		/*
			Write your code.
		*/
	}
}

输出格式

为了减小输出量,记第 ii 次询问的答案为 pip_i,你只需要输出 $(1\times p_1)\oplus (2\times p_2)\oplus\dots (q\times p_q)$ 的值。其中 \oplus 表示二进制异或操作。

样例 #1

样例输入 #1

1 1 1 1
12345678910

样例输出 #1

59

数据范围与约定

本题采用捆绑测试。

对于 100%100\% 的数据保证 k106,q5×107k\le10^6, q\leq5\times 10^7

子任务编号 q=q= kk\leq 分数
11 5×1065\times 10^6 10610^6 3030
22 5×1075\times 10^7 7070

[YDRG#002] 提瓦特环游记(下) · 云斗杯 · 八月 Golden 组模拟赛

未参加
状态
已结束
规则
北斗IOI
题目
6
开始于
2023-8-8 18:00
结束于
2023-8-8 22:30
持续时间
4.5 小时
主持人
参赛人数
299