[ARC092D] Two Sequences

[ARC092D] Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

难度:\(4.0\)

  • Problem Statement

You are given two integer sequences, each of length \(N\): \(a_1, \cdots ,a_N\) and \(b_1, \cdots ,b_N\).

There are \(N^2\) ways to choose two integers \(i\) and \(j\) such that \(1 \leq i,j \leq N\). For each of these \(N^2\) pairs, we will compute \(a_i+b_j\) and write it on a sheet of paper. That is, we will write \(N^2\) integers in total.

Compute the XOR of these \(N^2\) integers.

给定两个长度为 \(n\) 的正整数数组 \(a,b\) ,求 \(\forall 1 \leq i,j \leq n\),\(a_i+b_j\) 在二进制下的异或和 。

  • Input

\(n\) 和两数组 \(a,b\) 。

  • Output

答案。

  • Sample Input

  • Sample Output

  • Constraints

\(1 \leq …

CSP-S 2019 退役游记 && 破百纪念

现在时间 UTC+8 18:18 2019/11/15,距 CSP-S 2019 还有约 14 个小时。

是时候,准备离开机房了。

(刚好也是本 blog100 篇文章,顺便纪念一下www

 …

Ablenet VPS 测评 k-opti 机房

日本 vps 也找了不少,一直在犹豫到底哪个比较好。

aws、sakura、kagoya、conoha、gmocloud、cloudgarage、idcf、webarena、阿里jp。。。。。。

不是太贵就是线路差,要不然就是对国人不大友好。

(有异想天开的同学,三色图上

日本回国直连线路主要有:BBTEC、NTT、IIJ、KDDI、163,这次的 Ablenet 就是双程 IIJ 路线。


 …

YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

时间限制:4444MS      内存限制:1048576KB

难度:\(7.2\)

  • 题目描述

由于本题之前被*了,所以现在数据就是随便造的,可能会因为太水又被艹     //给出题人留点面子吧qwq

YJC 在 AK 了一场校内之后,对其中的一题(P2036 「A Simple Data Structure Problem II 」)产生了兴趣。

于是他出了一题加强版(P4316 「ASDSP VII —— YJC树」),然而,他还是觉得这个加强版太简单啦!!!

所以,这次,他不仅把 \(K \leq 5\) 往后面加了三个零变成了 \(K \leq 5000\) ,还对询问做了一点修改!

喜欢差分的 YJC 有一个长度为 \(N\) 的数组 \(c\),初始值都为 \(0\),下标编号为 \(1, 2, \cdots, N\) 。

现在 YJC 忙着 AK CSP-S2019,没空验证数据的正确性,所以只能把这个重任交给了你 —— ******,希望你能写一个程序帮他实现以下的几个操作:

\(opt=1\),给定 \(L, R\),输出 \(\sum\limits_{i=L}^R c_i\) 的值对 \(998244353\) 取模后的结果;

\(opt=0\),给定 \(L, R\) 以及 \(K\) 次多项式 \(f(x)=\sum\limits_{k=0}^K a_kx^k\),对 \(c_L, c_{L+1}, \cdots, c_R\) 分别加上 \(f(1), f(2), \cdots, f(R-L+1)\) 的值。

  • 输入格式

第一行两个正整数 \(N, Q\) ,分别表示区间范围 \([1, N]\) 及询问数 \(Q\) 。

接下来,每行(除了每个 \(opt=0\) 操作的下一行)的第一个数 \(opt\) 表示操作类型。

若 \(opt=0\),则接下来有两个正整数 \(L, R\) 表示操作的区间 \([L, R]\)。紧接着下一行的第一个整数 \(K\) 表示多项式的最高次数为 \(K\) ,接下来 \(K+1\) 个整数 \(a_0, a_1, \cdots, a_K\) 分别表示多项式 \(f(x)= \displaystyle\sum\limits_{k=0}^K a_kx^k\) 的系数;

若 \(opt=1\),则接下来有两个正整数 \(L, R\) 表示询问的区间 \([L, R]\)。

因为 YJC 忙着 AK CSP-S2019(之前说过了),所以他一不小心把数据给加密了。

记 …

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

时间限制:2000MS      内存限制:524288KB

难度:\(6.5\)

  • 题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\),有 \(m\) 次操作。格式如下:

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

  • 输入格式

第一行两个正整数 \(n,m\),表示序列长度和操作次数。

第二行 \(n\) 个正整数,第 \(i\) 个数为 \(a_i\),表示序列初始值。

接下来 \(m\) 行每行四个正整数,表示操作,含义如题目所示。

  • 输出格式

对于每个询问,输出一行一个正整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

对于 \(20\%\) 的数据,\(1 \leq …

YZOJ P4621 [CSP-S 2019 四校联训 Round 1]生日悖论

YZOJ P4621 [CSP-S 2019 四校联训 Round 1]生日悖论

时间限制:1000MS      内存限制:131072KB

难度:\(5.0\)

  • 题目描述

一共有 \(N\) 种数字,所以按照包含数字的集合分类,可能有 \(2^N\) 类不同的集合。每个集合包含一种特定的数字的概率都是 \(\displaystyle\frac{1}{2}\) 。

随机取其中 \(k\) 个集合,请你帮忙算一下其中存在两个集合完全相同的概率。

  • 输入格式

一行两个整数 \(N,k\) 。

  • 输出格式

两个正整数,分别表示概率(最简分数)的分子和分母。分别对 \(10^6+3\) 取模吧。

  • 数据规模与约定

\(1 \leq N \leq 10^{18}\),\(2 \leq k \leq 10^{18}\) 。

 

 

Source: CodeForces 711E ZS and The Birthday Paradox

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列

时间限制:4000MS      内存限制:524288KB

难度:\(7.0\)

  • 题目描述

给定一颗 \(n\) 个点的树。每个点都一个正整数点权 \(A_i\),你需要支持以下两种操作:

1、询问点 \(x\) 和点 \(y\) 之间的路径上的所有点(包括点 \(x\) 和点 \(y\) )的点权是否构成一个从 \(1\) 开始的排列。

2、将 \(A_x\) 修改为 \(y\)。

  • 输入格式

第一行一个正整数 \(T\) 表示数据组数。

接下来一行输入两个正整数 \(n,q\) 表示数的点数和询问个数。

接下来一行 \(n\) 个正整数,第 \(i\) 个正整数表示 \(A_i\) 的初值。

接下来 \(n-1\) 行每行两个正整数 \(u,v\) 表示树上的一条边 \((u,v)\) 。

接下来 \(n\) 行每行三个正整数 \(tp,x,y\) 表示一个操作,其中 \(tp\) 表示操作种类。

  • 输出格式

对于每一个操作 \(1\) 如果符合条件,输出 Yes ,否则输出 No 。…

YZOJ P4587 斐波那契数列

YZOJ P4587 斐波那契数列

时间限制:1234MS      内存限制:43210KB

难度:\(6.5\)       (既然是自己搬的题还是正常一点吧w)

  • 题目描述

定义模意义下的递推数列 \(\displaystyle f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.\),其中模数为 \(1000000009\) 。

给定整数 \(c\)(\(0 \leq c < 1000000009\)),求出它最早出现在数列的哪个位置,并输出下标。

若 \(c\) 永远不会出现在此数列的任一位置,则输出 \(-1\) 。

  • 输入格式

多组数据。

第一行一个正整数 \(T\) (\(0 < T \leq 100\)) 表示 \(T\) 组数据。

接下来 \(T\) 行每行一个数表示每组数据的 \(c\) 。

  • 输出格式

对于每组数据,输出一行一个数表示答案。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 5104…

YZOJ P4444 [APIO2019]路灯

YZOJ P4444 [APIO2019]路灯

时间限制:5000MS      内存限制:524288KB

难度:\(7.0\)

  • 题目描述

一辆自动驾驶的士正在 \(Innopolis\) 的街道上行驶。该街道上有 \(n+1\) 个停车站点,它们将街道划分成了 \(n\) 条路段。每一路段都拥有一个路灯。当第 \(i\) 个路灯亮起,它将照亮连接第 \(i\) 与第 \(i+1\)个站点的路段。否则这条路段将是黑暗的。

出于安全性的考虑,自动驾驶的士只能行驶在被照亮的路段上。换言之,的士能从站点 \(a\) 出发到达站点 \(b\) \((a<b)\) 的条件是:连接站点 \(a\) 与 \(a+1\),\(a+1\) 与 \(a+2, \cdots ,b-1\) 与 \(b\) 的路段都被照亮。

在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。

现在给定 \(0\) 时刻时,街道上路灯的初始状态。之后 \(1,2,\cdots,q\) 时刻,每时刻会发生下列两种事件之一:

\(toggle i\):切换第 \(i\) 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。

\(query a b\):自动驾驶的士部门的负责人想知道,从 \(0\) 时刻起到当前时刻,有多少个时刻满足:自动驾驶的士能够从站点 \(a\) 出发到达站点 \(b\) 。

请你帮助自动驾驶的士部门的负责人回答他们的问题。

  • 输入格式

第一行包含两个整数 \(n\) 和 \(q\) \((1 \leq n,q \leq 300000)\) —- 表示路灯的数量与时刻数。

第二行包含一个字符串 \(s\) 表示路灯的初始状态 \((\left|s\right| = n)\), \(s_i\) 为 \(1\) 表示第 \(i\) 个路灯初始时亮起; \(s_i\) 为 \(0\) 表示第 \(i\) 个路灯初始时熄灭。

接下来 \(q\) 行每行描述一个时刻的事件。第 \(i\) 行描述时刻 \(i\) 所发生的事件。

\(toggle i\) \((1 \leq i \leq n)\):该时刻切换了第 \(i\) 个路灯的状态。

\(query a b\) \((1 \leq a < b \leq n+1)\):计算从 \(0\) 时刻起到该时刻,共有多少个时刻满足的士能从站点 \(a\) 出发到达站点 \(b\) 。

至少有一个时刻的事件是 \(query\) 。

  • 输出格式

对于每个 \(query\) 的事件,输出一行单个整数,表示该问题的答案。…