咕咕了好久才写的博客。。。

CSP\text{CSP} 炸成狗。。

Day 1\text{Day}\ 1

T1\text{T}1 格雷码

题意：通常，人们习惯将所有 nn 位二进制串按照字典序排列，例如所有 2 位二进制串按字典序从小到大排列为：00，01，10，11。

格雷码（Gray Code）是一种特殊的 nn 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。

所有 2 位二进制串按格雷码排列的一个例子为：00，01，11，10。

nn 位格雷码不止一种，下面给出其中一种格雷码的生成算法：

  1. 1 位格雷码由两个 1 位二进制串组成，顺序为：0，1。
  2. n+1n + 1 位格雷码的前 2n2^n 个二进制串，可以由依此算法生成的 nn 位格雷码（总共 2n2^n 个 nn 位二进制串）按顺序排列，再在每个串前加一个前缀 0 构成。
  3. n+1n + 1 位格雷码的后 2n2^n 个二进制串，可以由依此算法生成的 nn 位格雷码（总共 2n2^n 个 nn 位二进制串）按逆序排列，再在每个串前加一个前缀 1 构成。

综上，n+1n + 1 位格雷码，由 nn 位格雷码的 2n2^n 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共 2n+12^{n+1} 个二进制串。另外，对于 nn 位格雷码中的 2n2^n 个 二进制串，我们按上述算法得到的排列顺序将它们从 0∼2n−10 \sim 2^n - 1 编号。

按该算法，2 位格雷码可以这样推出：

  1. 已知 1 位格雷码为 0，1。
  2. 前两个格雷码为 00，01。后两个格雷码为 11，10。合并得到 00，01，11，10，编号依次为 0 ~ 3。

同理，3 位格雷码可以这样推出：

  1. 已知 2 位格雷码为：00，01，11，10。
  2. 前四个格雷码为：000，001，011，010。后四个格雷码为：110，111，101，100。合并得到：000，001，011，010，110，111，101，100，编号依次为 0 ~ 7。

现在给出 nn，kk，请你求出按上述算法生成的 nn 位格雷码中的 kk 号二进制串。

解析：考场上用二分做的，就是一个很简单的模拟，但是一定注意要开 unsigned long long！！还有 1ull 也不能忘！！！否则就会像我一样丢掉 55 分。

然而考完后发现 OI Wiki\text{OI Wiki} 上面居然讲过格雷码！！！，答案原来就是 k⨁⌊k2⌋k\bigoplus \lfloor\frac{k}{2}\rfloor。直接暴力求解然后输出每一位即可。。。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=100010;
const double Pi=acos(-1.0);
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
unsigned long long n,k;
int main()
{
	scanf("%llu%llu",&n,&k);
	k=k^(k>>1);
	for(int i=n-1;i>=0;i--)
		printf("%llu",(k>>i)&1);
	return 0;
}

T2\text{T2} 括号树

题意：本题中合法括号串的定义如下：

  1. () 是合法括号串。
  2. 如果 A 是合法括号串，则 (A) 是合法括号串。
  3. 如果 A，B 是合法括号串，则 AB 是合法括号串。

本题中子串与不同的子串的定义如下：

  1. 字符串 S 的子串是 S 中连续的任意个字符组成的字符串。S 的子串可用起始位置 ll 与终止位置 rr 来表示，记为 S(l,r)S (l, r)（1≤l≤r≤∣S∣1 \leq l \leq r \leq |S |，∣S∣|S | 表示 S 的长度）。
  2. S 的两个子串视作不同当且仅当它们在 S 中的位置不同，即 ll 不同或 rr 不同。

一个大小为 nn 的树包含 nn 个结点和 n−1n − 1 条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。

小 Q 是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为 nn 的树，树上结点从 11 ∼ nn 编号，11 号结点为树的根。除 11 号结点外，每个结点有一个父亲结点，uu（2≤u≤n2 \leq u \leq n）号结点的父亲为 fuf_u（1≤fu<u1 ≤ f_u <u）号结点。

小 Q 发现这个树的每个结点上恰有一个括号，可能是( 或)。小 Q 定义 sis_i 为：将根结点到 ii 号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。

显然 sis_i 是个括号串，但不一定是合法括号串，因此现在小 Q 想对所有的 ii（1≤i≤n1\leq i\leq n）求出，sis_i 中有多少个互不相同的子串是合法括号串。

这个问题难倒了小 Q，他只好向你求助。设 sis_i 共有 kik_i 个不同子串是合法括号串， 你只需要告诉小 Q 所有 i×kii \times k_i 的异或和，即：

(1×k1) xor (2×k2) xor (3×k3) xor ⋯ xor (n×kn) (1 \times k_1)\ \text{xor}\ (2 \times k_2)\ \text{xor}\ (3 \times k_3)\ \text{xor}\ \cdots\ \text{xor}\ (n \times k_n)

其中 xor\text{xor} 是位异或运算。

解析：

手推可以发现一个结论：

一个后括号如果能匹配一个前括号，假设这个前括号的前 11 位同样有一个已经匹配了的后括号，那么我们势必可以把当前的匹配和之前的匹配序列合并，当前的这个后括号的贡献值，其实就等于前面那个后括号的贡献值 +1+1 。

然后通过栈来维护前括号的位置，直接搜一遍即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,k[501010],ans;
long long stack[501010],top;
long long p[501010],fa[501010];
long long head[501010],cnt;
char s[501010];
struct node
{
	int next;
	int to;
}e[1001010];
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void dfs(int u)
{
	int r=0;
	if(s[u]==')')
	{
		if(top)
		{
			r=stack[top];
			p[u]=p[fa[r]]+1;//u节点贡献值
			top--;
		}
	}
	else if(s[u]=='(')
		stack[++top]=u;
	k[u]=k[fa[u]]+p[u];//跑到u时的答案，即贡献值的总和
	for(int i=head[u];i;i=e[i].next)
		dfs(e[i].to);
	if(r!=0)
		stack[++top]=r;//回溯，保持栈原来状态，重新把栈顶压回去(右括号)
	else if(top)//否则是左括号，回到原来状态，退栈
		top--;
}
int main()
{
	scanf("%lld\n",&n);
	scanf("%s",s+1);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		add(x,i);
		fa[i]=x;
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		long long q=i*k[i];
		ans=ans^q;
	}
	printf("%lld",ans);
	return 0;
}

Day 2\text{Day}\ 2

T4\text{T4} Emiya 家今天的饭

~T3\text{T3} 太难了，咕咕~

题意：Emiya 是个擅长做菜的高中生，他共掌握 nn 种烹饪方法，且会使用 mm 种主要食材做菜。为了方便叙述，我们对烹饪方法从 1∼n1 \sim n 编号，对主要食材从 1∼m1 \sim m 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 ai,ja_{i,j} 道不同的使用烹饪方法 ii 和主要食材 jj 的菜（1≤i≤n,1≤j≤m1 \leq i \leq n, 1 \leq j \leq m），这也意味着 Emiya 总共会做 ∑i=1n∑j=1mai,j\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} a_{i,j} 道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 kk 道菜的搭配方案而言：

  • Emiya 不会让大家饿肚子，所以将做至少一道菜，即 k≥1k \geq 1
  • Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同
  • Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即 ⌊k2⌋\lfloor \frac{k}{2} \rfloor 道菜）中被使用

这里的 ⌊x⌋\lfloor x \rfloor 为下取整函数，表示不超过 xx 的最大整数。

这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。

Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数 998,244,353998,244,353 取模的结果。

解析：

一道容斥 DP 问题，比往年 Day2T1\text{Day2T1} 要难，但还可以接受。

题目要求求每行选一个，每列选不超过一半的方案数，并且可知如果不满足条件，则有且只有一行选了超过一半，因为不可能有两行同时选超过一半，可以得到，题目要求的方案数为每行选一个的总方案数减去每行选一个，且某一列选了超过一半的方案数。

首先对于每行选一个的方案数，我们用 g[i][j]g[i][j] 代表前 ii 行选了 jj 个的方案数，设 sum[i]sum[i] 为第 ii 行的和，可以得到状态转移方程为：

g[i][j]=g[i−1][j]+g[i−1][j−1]×sum[i](i∈[1,n],j∈[0,n]) g[i][j]=g[i-1][j]+g[i-1][j-1]\times sum[i](i\in [1,n],j\in[0,n])

即对于第 ii 行，选或不选。

初始化 g[0][0]=1g[0][0]=1，毕竟不选也是 11 种方案。

然后就是求每行选一个，且某一列选了超过一半的方案数。

首先枚举哪一列超过了一半，设为第 pp 列。设 f[i][j][k]f[i][j][k] 为前 ii 行选了 jj 个 pp 列的和 kk 个其他列的方案数，也可以很容易得到状态转移方程：

f[i][j][k]=f[i−1][j][k]+f[i−1][j−1][k]×a[i][p]+f[i−1][j][k−1]×(sum[i]−a[i][p]) f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k]\times a[i][p]+f[i-1][j][k-1]\times (sum[i]-a[i][p])

即对于第 ii 行，不选，选第 pp 列和不选第 pp 列。

记得每次枚举 pp 时要清空 ff 数组。初始化 f[0][0][0]=1f[0][0][0]=1。

但是这种方法得时间复杂度为 O(n3m)O(n ^3 m)，只能拿到 8484 分。

我们发现 ff 数组中我们并不在乎 jj 与 kk 得具体值，只关心它们的大小关系是否符合，所以我们可以优化至二维。

设 f[i][j]f[i][j] 表示前 ii 行选 pp 列的个数比其他列多了 jj 个的方案数，由于第二维可能是负数，所以平移下标。

状态转移方程也很简单：

f[i][j]=f[i−1][j]+a[i][p]×f[i−1][j−1]+(sum[i]−a[i][p])×f[i−1][j+1] f[i][j]=f[i-1][j]+a[i][p]\times f[i-1][j-1]+(sum[i]-a[i][p])\times f[i-1][j+1]

依然要记得清空和初始化，而且记得枚举时要统计答案，因为每一列的答案不一样。

最后得到的两个相减就行了。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=110,maxm=2010;
const int mod=998244353;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m;
long long a[maxn][maxm],sum[maxn],ans;
long long f[maxn][maxm<<1],g[maxn][maxm];//f第二维为了避免负数下标，整体下标平移n
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%lld",&a[i][j]);
			sum[i]=(sum[i]+a[i][j])%mod;
		}
	g[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=n;j++)
		{
			g[i][j]=g[i-1][j];
			if(j>0)
				g[i][j]=(g[i][j]+g[i-1][j-1]*sum[i]%mod)%mod;
		}
	for(int i=1;i<=n;i++)
		ans=(ans+g[n][i])%mod;
	for(int k=1;k<=m;k++)
	{
		memset(f,0,sizeof(f));
		f[0][n]=1;
		for(int i=1;i<=n;i++)
			for(int j=n-i;j<=n+i;j++)
				f[i][j]=(f[i-1][j]+f[i-1][j-1]*a[i][k]%mod+f[i-1][j+1]*(sum[i]-a[i][k])%mod)%mod;
		for(int i=1;i<=n;i++)
			ans=(ans-f[n][n+i]+mod)%mod;
	}
	printf("%lld",(ans%mod+mod)%mod);
	return 0;
}

T5\text{T5} 划分

题意：2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 nn 组数据，数据从 1∼n1 \sim n 编号，ii 号数据的规模为 aia_i。

小明对该题设计出了一个暴力程序，对于一组规模为 uu 的数据，该程序的运行时间为 u2u^2。然而这个程序运行完一组规模为 uu 的数据之后，它将在任何一组规模小于 uu 的数据上运行错误。样例中的 aia_i 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和，小明将让新数据的规模能够递增。

也就是说，小明需要找到一些分界点 1≤k1<k2<⋯<kp<n1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n，使得

∑i=1k1ai≤∑i=k1+1k2ai≤⋯≤∑i=kp+1nai \sum_{i=1}^{k_1} a_i \leq \sum_{i=k_1+1}^{k_2} a_i \leq \cdots \leq \sum_{i=k_p+1}^{n} a_i

注意 pp 可以为 00 且此时 k0=0k_0 = 0，也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化

(∑i=1k1ai)2+(∑i=k1+1k2ai)2+⋯+(∑i=kp+1nai)2 (\sum_{i=1}^{k_1} a_i)^2 + (\sum_{i=k_1+1}^{k_2} a_i)^2 + \cdots + (\sum_{i=k_p+1}^{n} a_i)^2

小明觉得这个问题非常有趣，并向你请教：给定 nn 和 aia_i，请你求出最优划分方案下，小明的程序的最小运行时间。

输入格式：第一行两个整数 n,typen, type。nn 的意义见题目描述，typetype 表示输入方式。

  1. 若 type=0type = 0，则该测试点的 aia_i 直接给出。输入文件接下来：第二行 nn 个以空格分隔的整数 aia_i，表示每组数据的规模。
  2. 若 type=1type = 1，则该测试点的 aia_i 将特殊生成，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 x,y,z,b1,b2,mx, y, z, b_1, b_2, m。接下来 mm 行中，第 i(1≤i≤m)i (1 \leq i \leq m) 行包含三个以空格分隔的正整数 pi,li,rip_i, l_i, r_i。

对于 type=1type = 1 的 23~25 号测试点，aia_i 的生成方式如下：

给定整数 x,y,z,b1,b2,mx, y, z, b_1, b_2, m，以及 mm 个三元组 (pi,li,ri)(p_i, l_i, r_i)。

保证 n≥2n \geq 2。若 n>2n \gt 2，则：

∀3≤i≤n,bi=(x×bi−1+y×bi−2+z) mod 230 \forall 3 \leq i \leq n, b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \bmod 2^{30}

保证 1≤pi≤n,pm=n1 \leq p_i \leq n, p_m = n。令 p0=0p_0 = 0，则 pip_i 还满足 ∀0≤i<m\forall 0 \leq i \lt m 有 pi<pi+1p_i \lt p_{i+1}。

对于所有 1≤j≤m1 \leq j \leq m，若下标值 i(1≤i≤n)i (1 \leq i \leq n) 满足 pj−1<i≤pjp_{j−1} \lt i \leq p_j，则有

ai=(bi mod (rj−lj+1))+lj a_i = \left(b_i \bmod \left( r_j − l_j + 1 \right) \right) + l_j

解析：

又是一道 DP 题，不过需要单调队列优化。

最基础的状态转移方程为：

dpj,k=min⁡(dpi,j+(sumk−sumj)2) dp _{j,k}=\min(dp _{i,j}+(sum _{k}-sum _{j}) ^2)

很明显会超时，考虑优化。

不难发现，转移的时候如果 jj 相同，那么随着 kk 的增大，ii 的取值范围也会增大，所以直接枚举 kk，挪动 ii，每次存储 min⁡(dpi,j)\min(dp _{i,j})，可以优化一部分。

继续分析题目，由 a2+b2≤(a+b)2a ^2+b ^2\le (a+b) ^2 可知，多分段会更优秀。

所以对于每一个 jj，直接取最大的可行的 ii 即可，我们用 sjs _{j} 代表最大的 ii 使得 sumj−sumi≥sumi−sumsisum _{j}-sum _{i}\ge sum _{i}-sum _{s _{i}}。

移项即可得到：

sumj≥2sumi−sumsi sum _{j}\ge 2sum _{i}-sum _{s _{i}}

又由于 sis _{i} 是递增的，我们可以直接用单调队列维护 ss 数组即可。

最后这道题要用高精度！！！我就用 int_128 代替好了。

#include<iostream>
using namespace std;
const int maxn=40000005;
const int mod=1073741824;
int n,type,a[maxn],b[maxn];
int q[maxn],s[maxn],head,tail;
long long sum[maxn];
long long calc(int x)
{
	return 2*sum[x]-sum[s[x]];
}
void print(__int128 x)
{
   	if(x<=9)
    	cout<<(int)x;
   	else
   	{
   		print(x/10);
   		cout<<int(x%10);
   	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>type;
	if(!type)
		for(int i=1;i<=n;i++)
			cin>>a[i];
	else
	{
		long long x,y,z,m,last=0;
		cin>>x>>y>>z>>b[1]>>b[2]>>m;
		for(int i=3;i<=n;i++)
			b[i]=(x*b[i-1]+y*b[i-2]+z)%mod;
		while(m--)
		{
			int p,l,r;
			cin>>p>>l>>r;
			for(int j=last+1;j<=p;j++)
				a[j]=(b[j]%(r-l+1))+l;
			last=p;
		}
	}
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&calc(q[head+1])<=sum[i])
			head++;
		s[i]=q[head];
		while(head<=tail&&calc(q[tail])>=calc(i))
			tail--;
		q[++tail]=i;
	}
	__int128 ans=0;
	for(int i=n;i;i=s[i])
		ans+=(__int128)(sum[i]-sum[s[i]])*(sum[i]-sum[s[i]]);
	print(ans);
	return 0;
}