关于 hack：

问题一可以用 64 999999999 和 64 10000000000 hack，你会发现它们的值差的不是一点两点。。。

（题目中提到格雷码的一个性质：相邻两个数码恰好一位的值不同）

问题二，可以用 64 18446744073709551615 hack，标答是 \(1\) 后面全是 \(0\) 。

T2 括号树

Problem Link 双倍经验 三倍经验

心路历程

我鄵cào，T2难度骤增。

先打了个链的部分分，推广到树上就是正解了。

但是我的树形DP（or 树上DP？反正都差不多）传参传的是个长度为 \(n\) 的 stack，应该会T。

（然后下来我就去跟 @Nefelibata 吹自己常数5e5）

链应该是 \(\Theta(n)\) 的，没问题，树有点险。

估分 \(\text{55+rp pts}\)

Solution

先把一条链的情况打出来再说。

因为已确定根节点为 \(1\) 且 \(f_i=i-1\)，所以 \(s_i=S_1\sim S_i\)，其中 \(s\) 的含义题目中有给出，\(S\) 为给定括号串。

\(k_i\) 的含义就可简化为 \(S_1\sim S_i\) 中的合法子串个数。

相信各位都做过括号匹配之类的题目，这里我们也用一个栈处理。

每遇到一个 \(\texttt (\) 就 push 进去，每遇到一个 \(\texttt )\) 就判断栈内是否有 \(\texttt (\) ，有就计算然后 pop。

因为要统计从 \(S_1\sim S_i\) 所有合法括号串，所以定义一个 \(cnt\) 表示从 \(S_1\sim S_i\) 的合法括号串个数，若当前字符可以完成一个匹配，则 cnt+=以第i个元素结尾的合法子串个数。

那么，这个“合法子串个数”应该怎样计算呢？

定义 \(lst\)，表示以当前元素的上一个元素结尾的合法子串个数。

若当前元素是 \(\texttt (\) ，把 \(lst\) 丢进栈里，记录如果当前 \(\texttt (\) 能被匹配，新增的合法括号串个数；

否则当前元素就和之前的合法子串挨不到一起了，\(lst\) 清零。（突然飚方言）

如果当前元素可以完成一个匹配，则栈顶记录的数就是和当前匹配上的括号紧挨着的之前的合法子串个数，由于当前又新增了一个匹配，记录最新的 \(lst\) 为栈顶元素 \(+1\)，同时这也是当前的 \(k_i\)。此时 cnt+=lst。

可得出以下代码：

//55pts 链 
namespace Task1{
	int lst,cnt;
	inline void solve(void){
		for(int i=1;i<=n;++i){
			if(s[i]=='('){
				stk.push(lst);
				lst=0;
			}
			else if(stk.size()){
				lst=stk.top()+1;
				cnt+=lst;
				stk.pop();
			}
			else lst=0;
			ans^=cnt*i;
		}
		printf("%lld",ans);
		return;
	}
}

然后直接把这些搬到树上即可。

其中，\(cnt\) 不能混合起来记了，必须每个点继承一下自己父亲结点的 \(cnt\)，然后自个儿记自个儿的。

\(lst\) 同理。

但是，由于作者清奇的思考方式与码风，她选择了把 \(cnt\) 改成数组，\(lst\) 改成 dfs 时传参。。。

总之，因为dfs在匹配过程中可能出现新增的 \(\texttt (\) 还没匹配完，留在栈里，或是后面一大堆 \(\texttt )\)，把之前的给匹配掉了，所以必须即时传参。

然后最后统一计算 cnt 值即可。

Code

差点被常数从 \(\Theta(n)\) 卡成 \(\Theta(n^2)\)。

#include
#include
#define int long long 
using std::stack;
const int maxn=5e5+5;
bool SF=1;	//Subtask Flag
int f[maxn];
char s[maxn];
int n,tot,ans;
stackstk;
int h[maxn],to[maxn],nxt[maxn];
inline void add(int x,int y){
	to[++tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
	return;
}
inline void read(int&x){
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch^48);
		ch=getchar();
	}
	return;
}
int cnt[maxn];
void dfs(int x,int lst,stackst){
	cnt[x]=cnt[f[x]];
	if(s[x]=='('){
		st.push(lst);
		lst=0;
	}
	else if(st.size()){
		lst=st.top()+1;
		cnt[x]+=lst;
		st.pop();
	}
	else lst=0;
	for(int i=h[x];i;i=nxt[i])
		dfs(to[i],lst,st);
	return;
}
inline void solve(void){
	dfs(1,0,stk);
	for(int i=1;i<=n;++i)
		ans^=i*cnt[i];
	printf("%lld",ans);
	return;
}
signed main(){
	freopen("brackets.in","r",stdin);
	freopen("brackets.out","w",stdout);
	read(n);
	scanf("%s",s+1);
	for(int i=2;i<=n;++i){
		read(f[i]);
		add(f[i],i);
	}
	solve();
	return 0;
}
//作者亲自实验：过是一定能过的，出题人不至于来卡我常；但常数确实大得像吃了屎一样。

T3 树上的数

Problem Link 双倍经验 三倍经验

心路历程

草草草还剩不到半个小时了快点暴力冲啊！！！

暴力打出来了，开森。

估分 \(\text{10 pts}\)。

Solution

我的暴力和题解说的全排暴力不太一样QwQ

正解先咕着，因为题解基于另一种暴力方法改良出正解导致我看不懂

\(\text{day 1}\) 考完即时评测可还行（（（

万恶的NOI赛制。

这个时候出成绩了。

草你奶奶我T1WA了？（刚刚是谁说T1有手就行的？）

估分：\(\text{100+(55+rp)+10}\approx \text{165 pts}\)

实际：\({\color{SkyBlue}95}+{\color{Orchid}100}+10=\text{205 pts}\)

\(\text{day 2 - 2:10 p.m.}\)

精准预测：上午考那么好，一定把脑子和 \(rp\) 都耗光了，下午一定被 @Nefelibata 吊打。

T1 Emiya 家今天的饭

Problem Link 双倍经验 三倍经验

心路历程

花了接近 \(\text{2.5h}\) 想正解，导致正解没想出来，其他题的暴力分也没时间骗。

时间安排及其不合理，导致与1=失之交臂。。。（莫名押韵）

猜出来了大概是个 \(\Theta(n^2\times m)\) 的DP。

Soution

部分参考了这位金钩爷的博客。

题意简化：

给定一个 \(n\times m\) 的矩阵，从中选取任意多个数（假设为 \(k\)），满足：

1. 每行最多一个数；
2. 每列最多 \(\large\lfloor\frac{k}{2}\rfloor\) 个数。

求 \(\sum\limits_{k=2}^n\) 这些数的乘积（后文称其为总方案数），结果对 \(998244353\) 取模。

首先，我们知道，条件 \(1\) 很好满足；关键是条件 \(2\)。

众所周知，这种求方案数之类的大概率是 DP（而且这道题看起来也挺像的）

首先有一个很简单，但是很重要的性质：不满足条件 \(2\) 的最多只有一列，因为总共就 \(k\) 个数，不可能分割成两个个数都超过 \(\large\lfloor\frac k2\rfloor\) 的组。

但这个性质是关于不满足条件 \(2\) 的，我们要求的却是同时满足条件 \(1\) 和条件 \(2\) 的，这时候怎么办呢？

很简单，我们算出满足条件 \(1\) 的总方案数，减去满足条件 \(1\) 且不满足条件 \(2\) 的方案数不就行了？

1. DP求解满足条件 \(1\) 的总方案数。

   \(dp_{i,j}\) 表示选到第 \(i\) 行，共选了 \(j\) 个数，满足条件 \(1\) 的总方案数。

   \[dp_{i,j}=dp_{i-1,j}+\sum\limits_{j=1}^mdp_{i-1,j-1}\times a_{i,j} \]

   小解释：\(dp_{i-1,j}\) 表示第 \(i\) 行不选的情况，\(\sum\limits_{j=1}^mdp_{i-1,j-1}\times a_{i,j}\) 表示第 \(i\) 行选 \(1\sim m\) 某一列上的数的情况。

   令 \(s_i=\sum\limits_{j=1}^ma_{i,j}\)，则可以优化为：

   \[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times s_i \]

   最终求得满足条件 \(1\) 的总方案数为 \(\sum\limits_{i=1}^mdp_{n,i}\)。

   注意，虽说这里求和是从 \(1\) 开始求的，但 \(j\) 还是得从 \(0\) 开始的异世界生活，所以在 \(j-1\) 那里要特判一下。

   时间复杂度 \(\Theta(n^2)\)。

2. DP求解满足条件 \(1\) 且不满足条件 \(2\) 的总方案数。

   我们设唯一不满足条件的列为 \(r\)。

   枚举每一个 \(r\)，对每一个不同的 \(r\) 进行一次DP。

   令 \(f_{i,j,k}\) 表示选到第 \(i\) 行，\(r\) 上有 \(j\) 个数，其他列一共选了 \(k\) 个数的方案数。

   \[f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k}\times a_{i,r}+f_{i-1,j,k-1}\times (s_i-a_{i,r}) \]

   小解释：\(f_{i-1,j,k}\) 表示第 \(i\) 行不选数，直接继承上一行的情况数；\(f_{i-1,j-1,k}\times a_{i,r}\) 表示选 \(a_{i,r}\) 的情况；\(f_{i-1,j,k-1}\times (s_i-a_{i,r})\) 表示选第 \(i\) 行其他列的情况总数。

   最终不合法方案总数为 \(\large\sum\limits_{j>k} f_{n,j,k}\)。

   为什么是 \(j>k\) ？

   由 \(j>\frac{j+k}2\) 变形得。（无视下取整，反正有没有都差不多）

   时间复杂度 \(\Theta(n^3)\)，在加上枚举 \(r\) 的一个 \(m\)，\(\Theta(n^3\times m)\)，直接炸掉。

   考虑优化。

   上面求不合法方案总数的限制条件是 \(j>k\)，意味着我们并不在意 \(j\) 和 \(k\) 的数值具体是多少，只关心它们之间的大小关系。

   所以可以把 \(f\) 变为二维，\(f_{i,j}\) 表示已经选到第 \(i\) 行，第 \(r\) 列上的数比其他列上的数多 \(j\) 的总情况数。

   则有：

   \[f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times a_{i,r}+f_{i-1,j+1}\times(s_i-a_{i,r}) \]

   最终答案为 \(\sum f_{n,i}\)。

   枚举到 \(i\) 时，\(j\) 最少可能是 \(0-i\)（全部选其他列上的），以及最多可能是 \(i-0\)（全部选 \(r\) 上的）。为了避免下标出现负数，我们把第二维的下标全部 \(+n\) 处理。（所以开数组时第二维也要多开一个 \(n\) 啦，不要像作者一样净犯这些SB错误还Debug了一个小时就离谱）

   单步时间复杂度 \(\Theta(n^2)\)，总时间复杂度 \(\Theta(n^2\times m)\)。

   可能有些同学会疑惑：\(a,b(a>b)\) 之间的差值与 \(a+1,b+1\) 的差值是一样的，像这样算总感觉怪怪的。。。

   可是，我们想想，就算我们把原来的 \(f_{i,a,b}\) 和 \(f_{i,a+1,b+1}\) 加在一起放在现在的 \(f_{i,a-b}\) 里面，未经优化的方式最终统计总方案数还是会把 \(f_{i,a,b}\) 和 \(f_{i,a+1,b+1}\) 加在一起，现在只是相当于提前加了而已，而且仔细分析式子，会发现不会重复计算。虽然看起来确实很怪异，但这种方法确实是正确的。

Code

#include
#include
#define int long long
const int mod=998244353;
int s[105];
int n,m,S,ans;
int a[105][2005];
int f[105][205],dp[105][105];
signed main(){
	#ifdef ONLINE_JUDGE
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);
	#endif
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%lld",&a[i][j]);
			s[i]=(s[i]+a[i][j])%mod;
		}
	}
	dp[0][0]=1;
	//Step 1: DP求解满足条件1的总方案数
	for(int i=1;i<=n;++i){
		for(int j=0;j<=i;++j){
			dp[i][j]=dp[i-1][j];
			if(j)dp[i][j]=(dp[i][j]+dp[i-1][j-1]*s[i])%mod;
			if(i==n&&j){S+=dp[i][j];S%=mod;}
		}
	}
	//Step 2: DP求解满足条件1且不满足条件2的总方案数
	for(int r=1;r<=m;++r){
		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][r]%mod
				+f[i-1][j+1]*(s[i]-a[i][r])%mod;
				f[i][j]%=mod;
			}
		}
		for(int i=1;i<=n;++i)
			ans=(ans+f[n][n+i])%mod;
	}
    //众所周知减法取模保险起见要先加模数
	printf("%lld",(S-ans+mod)%mod);
	return 0;
}

T2 划分

Problem Link 双倍经验 三倍经验

心路历程

距离考试结束还有不到半个小时。

心灰意冷地打开T2。

草！我做过这道题的简化版！推的式子还在U盘里！

此生无憾草你妈要不是旁边的 @Nefelibata 一直用正义猥琐的目光盯着我的电脑屏幕上的题解劳资直接干翻全场！！！

然后在 @Nefelibata 正义的目光下最终没能看成。

Solution

DP。

设 \(s_i\) 表示 \(\sum\limits_{j=1}^ia_j\)，\(d_i\) 为前 \(i\) 个数据的最小花费，\(h_i\) 表示第 \(i\) 个数据分配完后，\(d_i\) 最小时，\(i\) 所在组的花费。

此时，以 \(j+1\) 为当前组起点，\(d_i=\min\{d_j+(s_i-s_j)^2\}\)。

有引理：

\(i\) 的最优决策，即令 \(d_i\) 值最小的 \(j\)，就是满足 \(h_j\leqslant s_i-s_j\) 的 \(\max\{j\}\)。

感性证明一下。

1. 证明满足条件的 \(\max\{j\}\) 会使 \(d_i\) 最小。

   如图：

   

   图中的 \(j\) 表示满足条件的 \(\max\{j\}\)。则：

   • 以 \(j\) 为上一分组终点，\(j+1\) 为当前分组起点的代价为：

     \((sumL+x)^2+sumR^2=sumL^2+2\times x\times sumL+x^2+sumR^2\)。

   • 以 \(j-1\) 为上一分组终点，\(j\) 为当前分组起点的代价为

     \(sumL^2+(x+sumR)^2=sumL^2+x^2+2\times x\times sumR+sumR^2\)。

   即比较 \(2\times x\times sumL\) 和 \(2\times x\times sumR\) 之间的大小。

   回归条件，由于 \(j\) 合法，即 \(h_j\leqslant s_i-s_j\)，换到本图中来说就是 \(sumL\leqslant sumR-x\)。

   变形得 \(sumL+x\leqslant sumR\)。题目保证了 \(x\geqslant1\)，得 \(sumL\leqslant sumR\)。

   同样因为 \(x\) 为正数，得 \(2\times x\times sumL\leqslant 2\times x\times sumR\)，即在 \(j\) 处划分更优。

2. 证明选择在 \(\max\{j\}\) 处划分不会让后面的答案更劣

   也许我们可以保证在 \(j\) 处分组可以让 \(d_i\) 最小，但这样会不会影响 \(i\) 之后的结果呢？

   答案是不会。

   \(j\) 大，意味着 \(j\) 与 \(i\) 的差距更小，也就是 \(h_i\) 更小，那后面满足条件 \(h_i\leqslant s_{i'}-s_i\) 的难度就会减小（因为 \(s_i,s_{i'}\) 的值是固定的），就可以划分更多组，答案最优。

   相信组数越多答案更优的原因大家都知道，但我还是得扯一下：

   \(a\) 和 \(b\) 分成两组的花费为 \(a^2+b^2\)，而它们合并为一组的花费为 \((a+b)^2=a^2+2\times a\times b+b^2\)。

   \(\because\) 题目保证 \(a,b\in \Z^+\)

   \(\therefore\) 前者更优

那么此时我们DP \(d\) 数组，暴力寻找 \(\max\{j\}\)，枚举 \(1\sim n\) 之间的每一个 \(i\)，转移 \(\Theta(n)\)，总时间复杂度 \(\Theta(n^2)\)。意味着此时我们已经获得了 \(\text{80 pts}\) 的好成绩。

然后这题据说是可以用一个长相清秀的单调队列来搞。

夹带私货???(●˙?˙●)???关于单调队列优化DP的更多内容见此 Link

根据单调队列优化DP的套路，要维护的是 \(j\) 递增且 \(s_j+h_j\) 递增的单调队列。（由 \(h_j 变形得）

其中我们允许存在不合法的 \(s_j+h_j\)。因为可能 \(s_j+h_j\geqslant s_i\) 但是 \(s_j+h_j 并且 \(s_j+h_j\) 之后的都比 \(s_{i+1}\) 大。

常规的单调队列优化，答案都在队头；

而这道题呢？因为队头可能不合法，也有可能队头，队头后面的一个元素，队头后面的后面的元素，\(\cdots\) 都合法（并且后面几个的 \(j\) 值还一定比队头大），所以不能简单粗暴地通过队头查答案。

可以通过判断队头后面的一个元素是否合法，合法就删除队头的方式维护队头。（因为队列中的 \(j\) 递增）

因为刚才证明过，不用担心删除队头对后面的答案带来的影响。

但是，作为一只优秀的deque，怎么会有“访问队头的后面一个元素”的操作？我们稍微换个方法，用 \(val\) 记录当前满足条件的 \(\max\{j\}\)，若队头也满足条件，更新 \(val\)。最后的 \(\max\{j\}\) 就是 \(val\)。

这是队头。

队尾呢，由于塞进去的 \(j\) 一定递增，所以只用考虑 \(s_j+h_j\) 的问题。若

\(s_j+h_j\) 比队尾大，直接塞后面就行了；

否则，删除队尾再塞进去。

咦？删除队尾？不会影响答案吗？

记队尾元素为 \(r\)。

删除队尾的情况意味着 \(r 且 \(s_r+h_r\geqslant s_j+h_j\)。

如果比较大的 \(s_r+h_r\) 都比 \(s_i\) 小，那么比较小的 \(s_j+h_j\) 更是比 \(s_i\) 小，且 \(j\) 的下标更大，更优。

所以删除 \(r\) 毛事都不会发生。

没加__int128，\(\text{88 pts}\)。时间复杂度 \(\Theta(n)\)。

好的，开始加 __int128 && 卡空间。（出题人卡空间可要点B脸吧）

首先不能开 \(h\) 和 \(d\)，用 \(lst_i\) 记录 \(i\) 的前驱（即 \(i\) 的 \(\max\{j\}\) 的值）

然后不用单独的 \(s\) 算前缀和， \(a\) 自给自足。

我们从最后的第 \(n\) 块开始往回找，不断地跳到自己的前驱（也就是上一次分组的地方），直到跳到 \(0\) 为止。

注意了，从始至终都只有最后计算答案的变量 \(ans\) 开了 __int128，其他都没有，开了会T。

好了，讲得差不多了，上代码。

Code

#include
typedef __int128 ll;
typedef long long lll;
int n,type,l,r,val;
/*略掉快读*/
namespace Task1{
    const int maxn=5e5+5;
    lll a[maxn],d[maxn],h[maxn],s[maxn],q[maxn];
    void solve(void){
        l=r=1;
        for(int i=1;i<=n;++i){
            read(a[i]);
            s[i]=s[i-1]+a[i];
            while(l<=r&&s[q[l]]+h[q[l]]<=s[i])
                val=q[l++];
            h[i]=s[i]-s[val];
            d[i]=d[val]+h[i]*h[i];
            while(l<=r&&s[q[r]]+h[q[r]]>=s[i]+h[i])
                r--;
            q[++r]=i;
        }
        printf("%lld",d[n]);
        return;
    }
}
namespace Task2{
    const lll maxn=4e7+5;
    const lll mod=1ll<<30;
    ll ans;
    lll a[maxn];
    int lst[maxn],q[maxn];
    int x,y,z,m,p,li,ri,lt;
    inline lll h(int x){return a[x]-a[lst[x]];}
    void solve(void){
        l=r=1;
        //这什么lj输入
        read(x);read(y);read(z);
        read(a[1]);read(a[2]);read(m);
        for(int i=3;i<=n;++i)
            a[i]=(x*a[i-1]+y*a[i-2]+z)%mod;
        for(int i=1;i<=m;++i){
            read(p);read(li);read(ri);
            for(int j=lt+1;j<=p;++j)
                a[j]=a[j]%(ri-li+1)+li+a[j-1];
            lt=p;
        }
        for(int i=1;i<=n;++i){
            while(l<=r&&a[q[l]]+h(q[l])<=a[i])
                val=q[l++];
            lst[i]=val;
            while(l<=r&&a[q[r]]+h(q[r])>=a[i]+h(i))
                r--;
            q[++r]=i;
        }
        while(n){
            ans+=(ll)h(n)*h(n);
            n=lst[n];
        }
        int s[31],top=0;
        while(ans){
            s[++top]=ans%10;
            ans/=10;
        }
        while(top)putchar(s[top--]+'0');
    }
}
int main(){
    #ifdef ONLINE_JUDGE
    freopen("partition.in","r",stdin);
    freopen("partition.out","w",stdout);
    #endif
    read(n);read(type);
    if(type)Task2::solve();
    else Task1::solve();
    return 0;
}

T3 树的重心

题都没看过，放弃了。

因为现在是凌晨 \(3\) 点，所以作者不想写结束语了。

end.