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 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 P3069 字符串匹配

YZOJ P3069 字符串匹配

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

难度:\(7.0\)

  • 题目描述

给出两个串 \(A\) 和 \(B\),串中仅包含小写字母和字符 *,其中 * 能匹配任意的小写字母(也可以匹配 *)。

请你求出如果以 \(A\) 为模板串,那么有哪些 \(i\) 使得 \(B[i,i+\left|A\right|)\) 可以与  \(A\) 匹配?

  • 输入格式

第一行 \(A\),第二行 \(B\) 。

  • 输出格式

按照从小到大输出所有 \(i\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于所有数据,\(\left|A\right|, \left|B\right| \leq 500000\) 。

 

 

 …

YZOJ P2050 [FJOI2013]圆形游戏

YZOJ P2050 [FJOI2013]圆形游戏

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

难度:\(8.0\)

  • 题目描述

在一个无穷大的桌面上有 \(n\) 个圆形,保证任意两个圆相离或者相含,不存在相切或相交。现在 Alice 和 Bob 在玩一个圆形游戏,以 Alice 为先手,双方以如下步骤轮流游戏:

1,选定一个圆 \(A\),把 \(A\) 以及所有完全在 \(A\) 内部的圆都删除;

2,如果在自己回合无法找到可删除的圆,则输掉比赛。

假设 Alice 和 Bob 都非常聪明,请问最终谁能够取得胜利?请编程输出最终获胜的人。

  • 输入格式

输入数据的第一行为一个正整数 \(T\),表示数据组数。

接下来 \(T\) 组数据,对于每组数据,第一行包含 \(1\) 个正整数 \(n\),表示圆形的个数。

之后 \(n\) 行,每行为 \(3\) 个整数 \(x\)、\(y\) 和 \(r\) ,分别表示圆形的圆心坐标以及圆的半径。

  • 输出格式

假设 Alice 最后获胜,则输出一行 “Alice”(不包括引号),否则输出 “Bob” 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(100\%\) 的数据满足 \(T \leq 100\),\(n \leq m20000\),\(\left|x\right|, \left|y\right|, r \leq 10^8\) 。

 

 

 …

YZOJ P2966 染色

YZOJ P2966 染色

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

难度:\(7.0\)

  • 题目描述

你有 \(n\) 只猫,每一只猫认识另一些猫。但若 \(a\) 猫认识 \(b\) 猫,\(b\) 猫不一定会认识 \(a\) 猫。

现在,你需要将每一只猫染成红色或绿色。你是否可以通过染色让每一只猫都认识偶数只和自己同色的猫呢?

  • 输入格式

第一行 \(n\);

接下来 \(n\) 行,每行第一个数 \(d_i\) 表示猫 \(i\) 认识的猫的个数,后面跟着 \(d_i\) 个数表示认识的猫是哪些。

  • 输出格式

达不到要求,输出 Impossible

否则第一行输出红色猫的个数,第二行输出哪些猫是红色(那么其他猫就是绿色)

可以输出任意方案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,\(n \leq 2000\) 。

 

 

 …

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 P3056 三角形最大面积

YZOJ P3056 三角形最大面积

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

出题人:chj2001         难度:\(4.5\)

  • 题目描述

给定平面上 \(n\) 个点,定义 \(f(A,B,C)=\frac{1}{2} \left| x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B) \right|\) 。

每次操作都会将坐标系顺时针旋转 \(\frac{\pi}{9}\) 弧度,直到与原坐标系重合。

计算每次操作前 \(f\) 的最大值,并输出所有最大值的总和。

  • 输入格式

第一行输入一个正整数 \(n\),表示点的数量;

接下来 \(n\) 行,每行两个整数 \(x_i, y_i\) 表示最开始建立的坐标系下点的坐标。

  • 输出格式

输出所有 \(f\) 最大值的总和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,\(3 \leq n \leq 10000, -10000 \leq x_i, y_i \leq 10000\) 。

 

 

 …

YZOJ P3098 [JLOI2016]成绩比较

YZOJ P3098 [JLOI2016]成绩比较

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

难度:\(6.0\)

  • 题目描述

G系共有 \(n\) 位同学,\(m\) 门必修课。这 \(n\) 位同学的编号为 \(0\) 到 \(n-1\) 的整数,其中B神的编号为 \(0\) 号。

这 \(m\) 门必修课编号为 \(0\) 到 \(m-1\) 的整数。一位同学在必修课上可以获得的分数是 \(1\) 到 \(U_i\) 中的一个整数。如果在门课上 A 获得的成绩均小于等于 B 获得的成绩,则称 A 被 B 碾压。

在B神的说法中,G系共有 \(k\) 位同学被他碾压(不包括他自己),而其他 \(n-k-1\) 位同学则没有被他碾压。D神查到了B神每门必修课的排名。这里的排名是指:如果B神某门课的排名为 \(R\),则表示有且仅有 \(R-1\) 位同学这门课的分数大于B神的分数,有且仅有 \(n-R\) 位同学这门课的分数小于等于B神(不包括他自己)。

我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足B神的说法,也能符合D神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

你不需要像D神那么厉害,你只需要计算出情况数模 \(10^9+7\) 的余数就可以了。

  • 输入格式

第一行包含三个正整数 \(n, m, k\),分别表示G系的同学数量(包括B神),必修课的数量和被B神碾压的同学数量。

第二行包含 \(m\) 个正整数,依次表示每门课的最高分 \(U_i\) 。

第三行包含 \(m\) 个正整数,依次表示B神在每门课上的排名 \(R_i\) 。保证 \(1 \leq R_i \leq n\)。

数据保证至少有 \(1\) 种情况使得B神说的话成立。\(n \leq 100, m \leq 100, U_i \leq 10^9\) 。

  • 输出格式

输出仅包括一行一个整数,表示成绩情况数对 \(10^9+7\) 取模的结果。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据,\(n, m \leq 20\),\(U_i \leq 100\);

对于 \(100\%\) 的数据,\(n,m \leq 100\),\(U_i \leq 10^9\),\(1 \leq R_i \leq n\),\(0 \leq k < n\) …

YZOJ P3527 [FJOI2018D1T3]城市路径问题

YZOJ P3527 [FJOI2018D1T3]城市路径问题

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

难度:\(6.5\)

  • 题目描述

给出一张 \(n\) 个点的有向图 \(G(V, E)\) 。对于任意两个点 \(u, v\) (\(u\) 可以等于 \(v\) ),\(u\) 向 \(v\) 的连边数为:\(\sum\limits_{i=1}^k {out[u, i] \times in[v, i]}\) 。

给定 \(k\) 和数组 \(out, in\) ,现在有 \(m\) 个询问,每次询问给出三个参数 \(u, v, d\),你需要回答从节点 \(u\) 出发,经过不超过 \(d\) 条边到达节点 \(v\) 的路径有多少种。

答案对 \(10^9+7\) 取模。

  • 输入格式

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

接下来 \(n\) 行,第 \(i\) 行有 \(2k\) 个整数,前 \(k\) 个整数描述 \(out[i][]\),后 \(k\) 个数描述 \(in[i][]\) 。

接下来一行一个整数 \(m\) 。

接下来 \(m\) 行,每行三个整数 \(u, v, d\),描述一组询问。

  • 输出格式

对于每个询问,输出一个方案数。由于答案可能太大,输出其除以 \(10^9+7\) 后的余数。

  • 样例输入


Read the rest