学长还是很良心的QAQ，前两题还是可以的QAQ，只不过自己又没有注意细节。。所以挂掉了。

——————————————————我是分割线——————————————————

T1.小 Z 学数学(math)

要说小 Z 最不擅长的学科，那一定就是数学了。这不，他最近正在学习加

法运算。老师为了考核小 Z，给他出了一个问题。

给定一个操作序列，每个操作形如 t a 。如果 t 是 0，那么意味着加上 a；

如果 t 是 1，那么意味着改成 a。那么问题来了，给定一开始有一个数字 0，按照

从左到右的顺序执行操作序列中[l,r]段的操作，最后得到的数字是什么？

为了确定小 Z 已经掌握了加法运算，老师给了他许多询问。小 Z 这下可慌

了，因为他昨天晚上都在 dota，没有学习，自然也就回答不出问题。他准备向你

求助，你能告诉他每个询问的答案吗?

由于数据过大，所以小 Z 告诉了你数据的生成方式，并且你只要告诉他所

有答案按照指定方式加密后的结果就行了。

[输入格式]

从 math.in 中读取数据。

一行三个数字 n,m,seed 表示操作数量和询问数量，以及用于生成接下来所需要

的数据的变量。

生成数据的模板在下发文件 math.cpp 中给出。

[输出格式]

假设 m 个询问按照输入的顺序分别是 a1,a2,…,am,你需要输出一个整数，它等于∑ 233^i*ai对 998244353 取膜的结果

[样例输入]

5 5 23333

[样例输出]

50333483

[样例解释]

获得的数据分别是

0 880345150

1 787931255

0 2943464295

1 876592220

0 2063957658

3 3

1 4

2 5

2 4

3 5

询问的答案是 2943464295,876592220,2940549878, 876592220, 2940549878

输出 50333483

[数据范围与约定]

对于 30%的数据 n,m<=5000

对于 100%的数据 n,m<=10^7 0<=seed<=10^9

——————————————————我是分割线——————————————————

这道题目虽然看起来很难，数据也很大，但是仔细一想，其实就是找到ri之前的最后一个赋值操作，把它的位置和li取个max，然后求前缀和就好了QAQ；比赛时没膜爆long long了。。

#include
     
      #include
      
       #define max(a,b) ((a)>(b)?(a):(b))#define MN 10000005using namespace std;const int mod=998244353;unsigned int seed,a[MN];unsigned long long sum[MN];int n,m,l[MN],r[MN],z[MN];bool type[MN];unsigned int GetNext(){    seed^=(seed<<7);    seed^=(seed>>8);    seed^=(seed<<13);    return seed;}int main(){    freopen("math.in","r",stdin);    freopen("math.out","w",stdout);    scanf("%d%d%u",&n,&m,&seed);    for(int i=1;i<=n;++i){        type[i]=GetNext()%2,a[i]=GetNext();        if(type[i]==1)z[i]=i;else z[i]=z[i-1];        sum[i]=sum[i-1]+a[i];    }    long long res=233,nn=0,ans=0;    for(int i=1;i<=m;++i)    {        l[i]=GetNext()%n+1,r[i]=GetNext()%n+1;        int tmp;        if(l[i]>r[i])tmp=l[i],l[i]=r[i],r[i]=tmp;        ans=(sum[r[i]]-sum[max(l[i],z[r[i]])-1])%mod;        nn=(nn+res*ans%mod)%mod,res=res*233%mod;    }    cout<<(nn+mod)%mod;    return 0;    fclose(stdin);    fclose(stdout);}
      
     

——————————————————我是分割线——————————————————

T2.小 Z 学英语(english)

好不容易混过了数学课，英语课又快开始了。小 Z 十分紧张，毕竟他还没

有背好要考的单词，所以他想争取在英语课之前背完单词。小 Z 要背的单词有 n

个，并且他们有着相同的长度。为了节约时间，小 Z 准备将一些循环同构的单词

一起背。

我们称两个单词循环同构，当且仅当满足至少一个下面的条件。

1） 两个单词相同

2） 把其中一个单词的最后一位接到最前面(例如”abc”变成”cab”)，得

到的单词和另一个单词循环同构。

例如”abc”和”abc”,”cab”,”bca”循环同构。

小 Z 现在想知道这些单词中有多少对<i,j>(i<j)，满足第 i 个单词和第 j 个单

词循环同构？

[输入格式]

从 english.in 中读取数据。

第一行两个数 n,m，表示有 n 个单词，每个单词的长度是 m 。

接下来 n 行，每行读入一个长度为 m 的单词，单词只包含小写字母。

[输出格式]

输出一个数字表示答案。

[样例输入]

4 4

abcd

acbd

bcda

dabc

[样例输出]

3

[样例解释]

abcd、bcda、dabc 循环同构，答案是 3

[数据范围与约定]

本题采用子任务制， 只有你通过一个 subtask 内所有的数据点才能得到这个数据

点对应的分数。

Subtask1 包含 30Points，满足 1<=n,m<=300

Subtask2 包含 30Points，满足 m<=5

Subtask3 包含 40Points 没有特殊限制条件

对于所有数据，满足 1<=n,m<=10^6 n*m<=10^6

——————————————————我是分割线——————————————————

神奇的题目，很自然的，我们会想到：如果能够把字符串变成按照字典序排序最小的表示就好了。

当然，对于这一类问题，我们有专门的方法：最小表示法（复杂度O（n））；但是这道题目我们也可以hash值的最小值来做。

显然我们需要hash m次该字符串。那么难点就在于我们如何通过上一次的hash值O(1)求出下一个hash值呢？

在这里我们假设hash[i]=hash[i-1]*173+ch[i]，那么我们就把j（假设我们把字符串的第j位作为开头）位之前的Hash值从hash[m]中减掉，然后把hash前移j位，再把前j位的hash值*m-j+1加上当前的hash值。

当然，这只是我的想法，正解并不是很懂。。。但是理论是没问题的QAQ。

然后我们让long long的Hash值自然溢出，搞个map。根据概率理论，不会有hash冲突。（可能性很小）

下面贴代码。（我以后会填坑的）

#include
     
      #include
      
     

——————————————————我是分割线——————————————————

T3.小 Z 学化学(chemistry)

小 Z 最喜欢的学科是化学，甚至参加了化学学科比赛，获得了优异的成绩。

但他更有兴趣探索宇宙的奥秘，这天他遇到了一个难题。

小 Z 利用 α-666 射线观察了一种结构未知的 β-233 分子，并且发现这个分子

的结构形成了一棵以 1 为根三叉树。 因为物质的平衡问题， 树上的每一个节点只

可能有 0 或者 3 个儿子。 这棵树上的每个叶节点都会有一些核能， 因此所有节点

都会因此获得一些能量值，而这个分子的能量值就等于根节点的能量值。

经过不断的探寻，小 Z 终于发现了能量值的奥秘。原来每个叶节点的能量值

就等于它的核能， 而每个非叶节点的能量值等于他的三个儿子的能量值的中位数。

小 Z 现在已经知道了所有叶子节点的核能值，也知道了这个分子能量值是多少，

但他可以运用一些新技术，交换其中部分节点的核能。

小 Z 想知道在任意交换的情况下，这个分子的能量值最大能是多少。这对他

的研究有着重要意义。

[输入格式]

从 chemistry.in 中读取数据。

第一行两个数字 n,m， 表示有 n 个节点， 有 m 个叶子节点的核能可以任意交换。

接下来 n 行，第 i 行描述第 i 个节点的信息。

如果这个节点是一个叶子结点，那么这一行包括两个整数，第一个数是-1，第二

个数 ai 表示这个节点的能量值。

否则的话，这一行包括三个不同的整数，表示这个节点的三个子节点。

最后一行 m 个数，表示可以任意交换的叶子节点的编号。

[输出格式]

输出一个数字，表示所有情况下分子的能量值的最大值。

[样例输入]

7 5

2 4 5

3 6 7

-1 1

-1 3

-1 4

-1 2

-1 5

3 4 5 6 7

[样例输出]

4

[样例解释]

不交换情况下能量值是 3。假如交换节点 4 和节点 7 的核能，那么能量值就变成

了 4，可以证明这是最大的能量值。

[数据范围与约定]

本题采用子任务制， 只有你通过一个 subtask 内所有的数据点才能得到这个数据

点对应的分数。

Subtask1 包含 20Points 满足 n,m<=8

Subtask2 包含 10Points 满足 m<=1

Subtask3 包含 20Points 满足 n<=100000 m<=5

Subtask4 包含 20Points 满足 n,m<=5000

Subtask5 包含 30Points 满足 n,m<=10^6

对于所有数据，满足 m<=n<=10^6 n>=1 0<=ai<=10^9

由于读入数据较大，建议使用较快速的读入方式。

——————————————————我是分割线——————————————————

这道题目，很显然我们有一个性质：如果根结点的值可以做到>=a，那么一定可以做到>=b(a>b),也就是单调性。

所以我们显然套个二分就好了，那么我们想一想，怎么判断根节点能否>=当前的mid呢？

显然，有m个节点可以交换，就说明，这m个节点我们可以填上所有需要交换的数，每一个数可以填一次。

我们把所有的数分成3种，>=当前的mid，<当前的mid

假如说，一个节点的3个节点中有两个数的能量值<mid，那么显然这个节点就取不到mid

所以我们dfs整棵树，进行树形DP，如果一个数是可以交换叶子节点的那么这个点的dp值为1，否则如果这个叶子节点的值<mid返回inf,>=mid返回0；

非叶子节点的点的dp值为子节点的dp的较小的两个点之和，然后我们判断一下能交换的点中权值>=mid的个数是否比dp[1]的权值大，如果大，那么就把右端点往左移，否则把左端点往右移。

下面贴代码

#include
     
      #include
      
       #define MN 1000005#define minn(a,b) ((a)<(b)?(a):(b))using namespace std;int n,m,cnt,ans,mid,x;int s[MN][3],q[MN],v[MN];bool mark[MN];void swap(int &a,int &b){a^=b,b^=a,a^=b;}int dp(int u){    if(s[u][0]==-1)return mark[u]?1:(v[u]>=mid?0:1e9);    else {        int s1=dp(s[u][0]),s2=dp(s[u][1]),s3=dp(s[u][2]);        if(s1>s2)swap(s1,s2);if(s2>s3)swap(s2,s3);if(s1>s2)swap(s1,s2);        return minn(n+1,s1+s2);        }}int main(){    freopen("chemistry.in","r",stdin);    freopen("chemistry.out","w",stdout);    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        scanf("%d",&s[i][0]);        if(s[i][0]==-1)scanf("%d",&v[i]);        else scanf("%d%d",&s[i][1],&s[i][2]);    }    for(int i=1;i<=m;i++)scanf("%d",&x),mark[x]=1,q[++cnt]=v[x];sort(q+1,q+cnt+1);    int l=1,r=1e9;    while(l<=r){        mid=l+r>>1;        if(dp(1)<=cnt-(lower_bound(q+1,q+cnt+1,mid)-q)+1)l=mid+1,ans=mid;        else r=mid-1;    }printf("%d\n",ans);    fclose(stdin);    fclose(stdout);}