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 P4587 斐波那契数列

YZOJ P4587 斐波那契数列

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

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

  • 题目描述

定义模意义下的递推数列 \(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 P3451 [SDOI2013]随机数生成器问题

YZOJ P3451 [SDOI2013]随机数生成器问题

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

难度:\(6.0\)

  • 题目描述

有一个随机数生成器,可以生成 \(0\) ~ \(p-1\) 之间的伪随机整数。在生成之前,需要设定一个随机数种子 \(k\) (\(0 \leq k < p\)),则生成器第 \(1\) 次生成的整数为 \(k\)。该随机数生成器有 \(2\) 个参数 \(a, b\),如果第 \(i\) 次生成的整数为 \(x\),则第 \(i+1\) 次生成的整数为 \((ax+b) \bmod p\) 。

现给定整数 \(t\) ,我们的问题是,该随机数生成器至少需要生成多少个数,才能生成得到 \(t\)?

对于给定的 \(p,a,b,k,t\) ,请计算要使随机数生成器生成整数 \(t\),所需生成数的次数的最小值。

  • 输入格式

多组数据。第一行一个整数 \(T\) 表示数据组数,\(T \leq 50\) 。

接下来 \(T\) 行,每行五个整数 \(p,a,b,k,t\) 表示一组数据,其中 \(0 \leq a,b,k,t < p\) 。

  • 输出格式

对于每组数据,将随机数生成器的最小生成次数输出到文件中。

如果该随机数生成器无法生成整数 \(t\),输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据,\(p \leq 100\) 。

对于另外 \(30\%\) 的数据,\(a=1\) 。

对于另外 \(30\%\) 的数据,\(b=0\) 。

对于 \(100\%\) 的数据,\(p \leq 10^9\) 且 \(p\) 是质数。

 

 …

YZOJ P3752 序列求差问题

YZOJ P3752 序列求差问题

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

出题人:Night        难度:\(6.0\)

  • 题目描述

有一个序列 \(x_1,x_2,\cdots,x_n\) 。

求有多少个从 \(1,2,\cdots,n\) 中取三个元素的排列 \((a,b,c)\) 满足 \(x_a=x_b-x_c\) 。

由于是排列,所以 \((a,b,c)\) 与 \((c,b,a)\) 视为两组解。

  • 输入格式

第一行一个整数 \(n\) 表示序列长度。

第二行为 \(n\) 个整数表示序列里的 \(n\) 个数。

  • 输出格式

一行一个正整数,表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据,\(1 \leq n \leq 500\);

对于 \(45\%\) 的数据,\(1 \leq n \leq 5000\);

对于 \(100\%\) 的数据,\(1 \leq n \leq 1000000\),\(0 \leq \left|x_i\right| \leq 100000\) 。

 

 

 …

YZOJ P2163 [THUSC2015]解密运算

YZOJ P2163 [THUSC2015]解密运算

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

难度:\(7.0\) (自评)

  • 题目描述

对于一个长度为 \(N\) 的字符串,我们在字符串的末尾添加一个特殊的字符 “.” 。之后将字符串视为一个环,从位置 \(1,2,3,\cdots,N+1\) 为起点读出 \(N+1\) 个字符,就能得到 \(N+1\) 个字符串。

比如对于字符串 “ABCAAA”,我们可以得到这 \(N+1\) 个串:

接着我们对得到的这 \(N+1\) 个串按字典序从小到大进行排序(注意特殊字符 “.” 的字典序小于任何其他的字符)结果如下:

最后,将排序好的 \(N+1\) 个串的最后一个字符取出,按照顺序排成一个新的字符串,也就是上面这个表的最后一列,就是加密后的密文 “AAAC.AB” 。

请通过加密后的密文求出加密前的字符串。

  • 输入格式

第一行有两个整数 \(N, M\),分别表示加密前的字符串长度和字符集大小,其中字符用整数 \(1,2,3,\cdots,M\) 编号,添加的特殊字符 “.” 用 \(0\) 编号。

第二行为 \(N+1\) 个整数,表示加密后的字符串。

  • 输出格式

输出仅一行,包含 \(N\) 个整数,用空格隔开,依次表示加密前字符串中每个字符的编号。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(N,M \leq 200000\) 。

 

 …

YZOJ P2697 画圆

YZOJ P2697 画圆

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

难度: \(5.1\)

  • 题目描述

在初中数学课上,\(Alkri\) 学习了圆的相关知识,他对与圆有关的问题更加感兴趣了。

\(Alkri\) 想在平面直角坐标系的第一象限中依次画 \(n\) 个与两坐标轴均相切的圆,其中,第 \(1\) 个圆的半径为 \(r\),之后的每个圆都比上一个圆大,且与上一个圆相切,也就是说,对所有整数 \(2 \leq i \leq n\),第 \(i\) 个圆的半径大于第 \(i-1\) 个圆的半径且与第 \(i-1\)个圆相切。

例如当 \(n=3\) 时,三个圆 \(C_1, C_2, C_3\) 如下图所示(由于 \(C_3\) 比较大,未画完整):

现在,\(Alkri\) 很好奇:第 \(n\) 个圆的半径 \(R\) 到底有多大?他知道 \(R\) 不一定是整数(真聪明!),并且可能非常大,所以只需要你保留 \(R\) 的整数部分(向下取整)的末尾 \(p\) 位数字即可。

  • 输入格式

输入仅一行,包含三个整数 \(n\),\(r\),\(p\),意义如题目所述。

  • 输出格式

输出仅一行一个整数,表示第 \(n\) 个圆的半径 \(R\) 的整数部分的末尾 \(p\) 位。注意当 \(R\) 的整数部分实际位数超过 \(p\) 时需要输满 \(p\) 位(即需要保留前导0),如果实际位数不满 \(p\) 位则不用补前导 0 。

  • 输入样例

  • 输出样例

  • 样例说明

第 \(10\) 个圆的半径整数部分为 \(38808989\),要求输出整数部分的末尾 \(5\) 位数,因此输出 \(08989\) 。注意保留前导 0 。

  • 数据规模与约定

 

 

 …

YZOJ P1800 质数生成器

[NOIP2015四校联训Day8]质数生成器

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

  • 题目描述

生成给定范围内的所有质数。

  • 输入格式

有多组数据。

输入数据第一行是一个整数\(T(T\leq10)\),表示测试数据的组数。

接下来\(T\)行,每行有两整数\(m, n\),表示要求生成质数的范围是\([m, n] (1 \leq m \leq n \leq 10^9, n-m \leq 10^6)\)

  • 输出格式

对于每一组测试数据,输出所有在\([m, n]\)中的质数\(p\),一行一个。

不同测试数据之间用一个空行分隔。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于\(30\%\)的数据,\(m < n \leq 10^3\);

对于\(50\%\)的数据,\(m < n \leq 10^6 且 n-m \leq 10^3\);

对于\(100\%\)的数据,\(m < n \leq 10^9 且 n-m \leq 10^6\);…