day1

t1

题目描述

求 \(\left(\sum\limits_{i_1=0}^{n_1-1}\sum\limits_{i_2=0}^{n_2-1}\cdots\sum\limits_{i_d=0}^{n_k-1}\max\left(0,(i_1\operatorname{xor} i_2\operatorname{xor} \cdots\operatorname{xor} i_d) - l\right)\right) \bmod p\)。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个正整数 \(T,d\)，分别表示包含的测试数据组数。和本组测试数据中伊煞梅尔所掌握的超空间维度。之后 \(T\) 行，每行包含 \(d+2\) 个非负整数，依次分别表示 \(n_1\cdots n_d\)，\(l\) 和 \(p\)。

输出 \(T\) 行，每行输出一个非负整数，表示答案对 \(p\) 取模之后的结果。

• 对于5%的测试数据，有 \(T=2,\prod\limits_{i=1}^dn_i≤10^9\)
• 对于另外 5% 的测试数据，有 \(d=1\)
• 对于另外 15% 的测试数据，有 \(d=2\)
• 对于另外 15% 的测试数据，有 \(d=3\)
• 对于另外 15% 的测试数据，有 \(d=4\)
• 对于另外 20% 的测试数据，有 \(l=0\)
• 对于 100% 的测试数据，有 \(1\le T \le 10, 1 \le d \le 10, 0 \le n_i \le 10^{18}, 0 \le l \le 10^9, 1 < p \le 10^9\)。

t2

输入：第一行 \(S\)，第二行 \(k\)。

给你字符串 \(S\)，求出最短的 \(S'\)，使得：

\(S\) 是 \(S'\) 的前缀（允许 \(S=S'\)），所有长度为 \(k\) 的小写字母字符串都是 \(S'\) 的一个子序列。

子任务 1（7 分）：\(k = 1\)。

子任务 2（13 分）：\(k \le 2\)。

子任务 3（20 分）：\(S\) 不包含字符 a。

子任务 4（20 分）：最短的 \(S'\) 满足 \(|S'| - |S| \le 1\)。

子任务 5（20 分）：\(|S|, k \le 2 \times 10^3\)。

子任务 6（20 分）：无特殊限制。

t3

给你一个 \(n-1\) 条边 \(n\) 个点的连通图，每条边有权值，一些边被定向，你需要把所有未定向的边定向使得最长链的长度（指每条边权值和）最小。

弱化版：UVA1380。

输入：第一行 \(n\)，后面 \(n-1\) 行 \(u_i,v_i,w_i,t_i\)，表示连接的两个点，权值，是否定向（\(t=1\)：\(u\to v\)，\(t=0\)：未知）。

\(n\le 15\)。12pts。

\(n\le 50\)。16pts。

\(n\le 300\)，\(w=1\)。13pts。

\(n\le 300\)。20pts。

\(n\le 2\times 10^5\)，\(u_i=i+1,v_i=i\) 或 \(u_i=i,v_i=i+1\)。15pts。

\(n\le 2\times 10^5\)。24pts。

t4

++ 语言程序

小 R 把用来给他的计算机编程的语言称为 ++ 语言（因为只支持加法的运算）。以下是一个 ++ 语言的例子：

每行写有一个语句，每个语句都以分号结尾（中间不能有空格等无关字符），程序执行时按照从上到下的顺序执行；

• 最基本的元素为数组 a，它的长度为 1000000（可用 a[0] 到 a[999999] 访问），下标只能是十进制常数，而不能是其他表达式（如不能写 a[a[0]] 的形式）；

• 数组 a 的每个元素为小于 998244353 的非负整数，程序开始执行时数组 a 的每个元素均为 0；

• 语句共有四种：输入语句、输出语句、加法语句、赋值语句；
  输入语句的格式如 input(a[x]);，表示从标准输入流读入一个数并存入 a[x]（输入的数一定是小于 998244353 的非负整数）；

• 输出语句的格式如 output(a[x]);，表示向标准输出流写入整数 a[x] 并换行；

• 加法语句的格式如 a[x]=a[y]+a[z];（其中 x、y、z 可以相同），表示计算 a[y] 与 a[z] 之和对 998244353 取模的结果后赋值给 a[x]。

• 赋值语句的格式如 a[x]=a[y];（其中 x、y 可以相同），表示将 a[y] 赋值给 a[x]。

小 R 规定，一个 ++ 语言程序所用的时间为它的加法语句条数（即执行的加法次数），而所用的空间为它所写入的数组元素个数。其中，一个数组元素被写入，是指该元素曾（至少一次）出现在输入语句中，或出现在加法语句、赋值语句的左侧。

例如，

input(a[1]);
input(a[2]);
a[1]=a[1]+a[2];
input(a[3]);
a[1]=a[1]+a[3];
output(a[1]);
input(a[4]);
a[5]=a[4];
a[5]=a[5]+a[3];
a[5]=a[5]+a[2];
output(a[5]);

的时间为 4，而空间为 5。

小 R 给你的任务

对于每个测试点，输入一个 ++ 语言程序，请你输出一个与之等价的程序，满足使用的时间与空间尽量小。详见下述：

输入格式
输入文件为 opt1.in 至 opt10.in。

每个输入文件的前 10 行中，每行输入 2 个整数，其中第 \(k\) 行输入的是 \(T_k,M_k\)

接下来若干行，输入一个 ++ 语言程序。

输出格式
输入文件为 opt1.out 至 opt10.out。

每个输入文件输出一个 ++ 语言程序。

你对于每个测试点的输出不得超过 8 MB。一般来说，一个能得到至少 1 分的输出答案不应当超出 8 MB，这只是为了限制大量无意义的赋值语句，而非出于其他目的。

day2

t1

咕。

t2

咕。

t3

咕。

t4

咕。

t5

咕。