专栏文章

0606

CCap1taL
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip4qmzp
此快照首次捕获于
2025/12/03 06:08
3 个月前
此快照最后确认于
2025/12/03 06:08
3 个月前
查看原文

NFLS T2 (AT_arc128_f)

有 NN 张编号为 11 到 NN 的卡片。第 ii 张卡片上写着整数 AiA_i。这里，NN 是偶数。
Snuke 和 Robot 将玩一个游戏，规则如下。
  • 游戏主宣布一个排列 (p1,p2,⋯ ,pN)(p_1,p_2,\cdots,p_N)，给 Snuke 和 Robot。
  • 然后，Snuke 和 Robot 轮流进行，Snuke 先开始。每个回合的规则如下。
    • Snuke 的回合：选择一张剩余卡片并烧掉。
    • Robot 的回合：选择具有最大 pip_i 的卡片 ii 并烧掉。
  • 当没有卡片剩余时游戏结束。
游戏的最终得分是 Snuke 吃掉的卡片上整数的总和。Snuke 将以最佳方式玩以最大化得分。
有 N!N! 个排列 pp 的 (1,2,⋯ ,N)(1,2,\cdots,N)。找到所有这些排列的最终得分总和，模 998244353998244353。
  • 1≤N≤1061 \leq N \leq 10^6
  • NN is even.
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • All values in input are integers.
NFLS 还要求支持动态修改 AiA_i

题解

好题，学到很多
先不考虑动态修改 aia_i
为方便令 n←n2n\leftarrow \frac{n}{2}
首先发现我们可以把每个 aia_i 的贡献拎出来。
具体地，若 aia_i 在 (2n)!(2n)! 个排列中的 XX 个里被烧掉了，那么显然它贡献的得分是 aiXa_iX
同时我们发现这样一来我们不关心 aia_i 是什么了，我们只关心相对大小关系
于是，如果能求出 fif_i 表示第 ii 大的数被用掉的排列数量，对 aa 降序排序，答案显然就是 ∑i=12nfiai\sum_{i=1}^{2n}f_ia_i，这样修改也是好做的。
问题转化成如何求出 fif_i
值域是 2n2n 还是太难做了，考虑求出前 kk 大的数被用掉的总次数 gk=∑i=1kfig_k=\sum_{i=1}^kf_i
这样一来，我们可以把所有 ≥k\ge k 的数看作 11，把所有 <k\lt k 的数看作 00，转变成了一个 0101 问题，gkg_k 就等于对于所有含有 kk 个 11 且长度为 2n2n 的 0101 序列做上述游戏，被 Snuke 选中的 11 的总数。同时我们不关心 0101 内部的具体数值，因此 gkg_k 还要乘上 k!(2n−k)!k!(2n-k)!
对式子的推导暂时到头了，现在我们需要来挖掘这个游戏的性质。容易发现前 22 个数里 Snuke 最多选 11 个，前 44 个里最多选 22 个，以此类推，前 2i2i 个数里最多选 ii 个。如果把 Snuke 选择的数看作 −1-1，没选的看作 +1+1，那我们需要保证所有前缀和均不小于 −1-1。
然而这样还是太抽象了，一个思路是倒着考虑后缀限制。为了第 ii 个选择的数的前缀和合法，它前面必须不选至少 i−1i-1 个数。因此第 ii 个数的选择范围是 [2i−1,n][2i-1,n]。
所以我们对于一个确定的 0101 序列有了一个确定的算法来求出会选几个 11
  • 每 22 个 0101 打包，不妨设每包有 cic_i 个 11，则一共有 nn 个包，∑inci=k\sum_i^nc_i=k
  • 倒着从 nn 到 11 遍历 ii
  • 先累加 cnt1←cnt1+cicnt_1\leftarrow cnt_1+c_i
  • 根据上面的结论，现在我们不得不取一个数。尝试 cnt1cnt_1 是否大于 00，如果是就可以取一个 11，否则就得取 00 了。
枚举所有 0101 现在就可以做到 O(22nn)O(2^{2n}n) 的时间求出 gkg_k 了，比 O(n!)O(n!) 好多了。我们尝试进一步优化
追踪 cnt1cnt_1 的变化，每次操作相当于 cnt1←max⁡(0,cnt1+ci−1)cnt_1\leftarrow\max(0,cnt_1+c_i-1)。我们把它搬到平面网格上。
转化成：
  • 起始位于 (0,0)(0,0)
  • 每次可以向右上、右、右下三个方向前进（分别对应 ci−1c_i-1 等于 {−1,0,1}\{-1,0,1\}）
  • 一共走 nn 步
  • 向右的方案系数是 22（对应 ci=1c_i=1，此时包内方案有 0101 和 1010 两种）
  • 向右上、右下的方案系数是 11
  • 如果走到了 xx 轴下方， 我们强行向上回到 xx 轴，并称这一步 "失败"（对应无法从 cnt1cnt_1 中取 11 的情况）
  • 否则，我们称这一步 "成功 "（对应从 cnt1cnt_1 中取 11 的情况）
这样一来，每条路径都对应了一种 cnt1cnt_1 的变化序列。这个变化序列所对应的 0101 序列数量就是每步的方案系数乘积，取出 11 的数量就是 "成功" 的步数。
因此现在可以枚举所有路径，可能比 22nn2^{2n}n 要快一些
这一步转化其实很有意思。
  • 枚举的是所有 0101 序列
  • 根据每个 0101 序列来计算一系列 cnt1cnt_1 的变化
  • 根据 cnt1cnt_1 的变化来求出我们取了多少 11
我们需要的只是最后的答案，而 0101 序列和 cnt1cnt_1 的变化并非一一对应，而是多对一的关系。这一步转化使得我们不必再枚举 0101 序列，转而考虑更好刻画的 cnt1cnt_1 变化问题——我们把后者成功放到了网格图上考虑，更直观了
现在要继续进一步优化。这个低于 xx 轴拉回的限制太抽象了，考虑直接不拉回会怎么样。容易发现，被拉回的步数等价于不拉回时的最小值。于是变成：
  • 起始位于 (0,0)(0,0)
  • 每次可以向右上、右、右下三个方向前进（分别对应 ci−1c_i-1 等于 {−1,0,1}\{-1,0,1\}）
  • 一共走 nn 步
  • 终点必须是 (n,k−n)(n,k-n)（因为 ∑i=1nci=k\sum_{i=1}^nc_i=k，所以向上总贡献是 kk，向下总贡献是 nn，落点在 k−nk-n）
  • 向右的方案系数是 22（对应 ci=1c_i=1，此时包内方案有 0101 和 1010 两种）
  • 向右上、右下的方案系数是 11
  • 对应的 0101 序列数量就是每步的方案系数乘积
  • 设走过的最小值为 LL，则取出 11 的数量就是 n+Ln+L
  • 这个路径对 gkg_k 的贡献是 k!(2n−k)!(n+L)(每步方案系数乘积)k!(2n-k)!(n+L)(每步方案系数乘积)
如果在给定 n,k,Ln,k,L 的情况下，我们能快速计算所有路径的方案系数乘积之和，我们就做完了。不妨设其为 S(n,k,L)S(n,k,L)
钦定最小值是 LL 不好考虑，我们尝试对于最小值 ≥L\ge L 的路径求出答案后差分，设其为 F(n,k,L)F(n,k,L)
为了解决掉这个最小值 ≥L\ge L 的限制，可以利用折线法做一个小容斥。
设不限制最小值时的答案为 G(n,k)G(n,k)，即从 (0,0)(0,0) 按刚才的方法走到 (n,k−n)(n,k-n) 的所有路径的方案系数乘积之和。我们需要从这里面去掉最小值 <L\lt L 的路径的答案。
对于每个最小值 <L\lt L 的路径，它一定会经过 y=L−1y=L-1 这条直线。找到它第一次访问 y=L−1y=L-1 的点，称其为 PP，我们沿 y=L−1y=L-1 对陈路径在 PP 后的部分，终点变为 (n,2(L−1)−(k−n))(n,2(L-1)-(k-n))。我们发现，所有从 (0,0)(0,0) 到新终点的路径都对应一条原问题的非法路径。证明可以直接考虑翻转回去。
于是 F(n,k,L)=G(n,k)−G(n,2L+2n−k−2)F(n,k,L)=G(n,k)-G(n,2L+2n-k-2)
问题最后变成怎么快速计算 G(n,k)G(n,k)。事实上我们要计算的是
[xk−n](x−1+2+x)n[x^{k-n}](x^{-1}+2+x)^n
很巧妙的一个式子，每步的选择变为了多项式每项的选择，纵坐标转化成了 xx 的幂次，方案系数转化为了 xx 的系数。
[xk−n](x−1+2+x)n=[xk−n]x−n(1+2x+x2)n=[xk](1+2x+x2)n=[xk](x+1)2n[x^{k-n}](x^{-1}+2+x)^n=[x^{k-n}]x^{-n}(1+2x+x^2)^n\\ =[x^{k}](1+2x+x^2)^n\\ =[x^{k}](x+1)^{2n}\\
我趣，二项式定理
G(n,k)=[xk−n](x−1+2+x)n=[xk](x+1)2n=(2nk)G(n,k)=[x^{k-n}](x^{-1}+2+x)^n=[x^{k}](x+1)^{2n}={2n\choose k} F(n,k,L)=G(n,k)−G(n,2L+2n−k−2)=(2nk)−(2n2L+2n−k−2)=(2nk)−(2nk+2−2L)F(n,k,L)=G(n,k)-G(n,2L+2n-k-2)={2n\choose k}-{2n\choose 2L+2n-k-2}={2n\choose k}-{2n\choose k+2-2L} S(n,k,L)=F(n,k,L)−F(n,k,L+1)=(2nk−2L)−(2nk+2−2L)S(n,k,L)=F(n,k,L)-F(n,k,L+1)={2n\choose k-2L}-{2n\choose k+2-2L}
那很爽了，我们可以计算 gkg_k
gk=k!(2n−k)!∑L=−nmin⁡(k−n,0)(n+L)S(n,k,L)=k!(2n−k)!∑L=−nk−n(n+L)((2nk−2L)−(2nk+2−2L))g_k=k!(2n-k)!\sum_{L=-n}^{\min(k-n,0)}(n+L)S(n,k,L)\\ =k!(2n-k)!\sum_{L=-n}^{k-n}(n+L)\left({2n\choose k-2L}-{2n\choose k+2-2L}\right)\\
注意 LL 的取值范围。L≤0L\le 0 显然，L≤k−nL\le k-n 是因为 n+Ln+L 需要 ≤k\le k，因为一共只有 kk 个 11，不能选更多了。
后面推式子部分是简单的。注意到 ∑L\sum_L 内是一个相减的形式，刚好可以随着 LL 增加两两抵消，最后做个前缀和就可以了。
修改的部分也是简单的。因为修改的差值很小，考虑每次给 ax+1a_x+1 怎么做，发现只有 O(1)O(1) 个变化，暴力做就可以了。总复杂度 O(n+q∣y∣)O(n+q|y|)
CPP
int fac[5000001];
int inv[5000001];
int C(int n,int m){
	if(n<m)	return 0;
	return mul(fac[n],inv[m],inv[n-m]);
}
int g[MAXN];
int f[MAXN];
int G(int n,int k){
	return C(2*n,k);
}
int F(int n,int k,int L){
	return rmv(G(n,k),G(n,2*(L-1)-(k-n)+n));
}
int S(int n,int k,int L){
	return rmv(F(n,k,L),F(n,k,L+1));
}

int n,q;
int a[MAXN];
void gen(){
	static int c[5000005];
	static int s[5000005];
	foru(i,0,2*n){
		c[i]=C(2*n,i);
	}
	s[0]=c[0],s[1]=c[1];
	foru(i,2,5*n){
		s[i]=add(s[i-2],c[i]);
	}
	auto qry=[](int l,int n)->int {
		int ret=s[l+2*(n-1)];
		if(l>=2)	mmv(ret,s[l-2]);
		return ret;
	};
	foru(k,1,n){
		mdd(g[k],mul(n,C(2*n,2*n-k)));
		mmv(g[k],mul(n,C(2*n,2*n+k+2)));
		mmv(g[k],mul(n-k,C(2*n,2*(n-k)+k)));
		mdd(g[k],mul(n+1,C(2*n,2*(n+1)+k)));
		mmv(g[k],qry(k+2*(n-k+1),(n+1)-(n-k+1)+1));
		// foru(L,n-k+1,n+1){
		// 	mmv(g[k],c[2*L+k]);
		// }
		mll(g[k],fac[k],fac[2*n-k]);
	}
	foru(k,n+1,2*n){
		mdd(g[k],mul(n,C(2*n,k)));
		mmv(g[k],mul(n,C(2*n,2*n+k+2)));
		mmv(g[k],mul(0,C(2*n,2*(0)+k)));
		mdd(g[k],mul(n+1,C(2*n,2*(n+1)+k)));
		mmv(g[k],qry(2+k,n));
		// foru(L,1,n+1){
		// 	mmv(g[k],c[2*L+k]);
		// }
		mll(g[k],fac[k],fac[2*n-k]);
	}
	foru(i,1,2*n){
		f[i]=rmv(g[i],g[i-1]);
	}
}

void solve(bool SPE){ 
	n=RIN/2,q=RIN;
	foru(i,1,2*n){
		a[i]=RIN;
	}

	fac[0]=1;
	foru(i,1,5000000){
		fac[i]=mul(fac[i-1],i);
	}
	inv[5000000]=qpow(fac[5000000],mod-2);
	ford(i,5000000-1,0){
		inv[i]=mul(inv[i+1],i+1);
	}
	
	gen();
	
	int ans=0;
	static int b[MAXN];
	foru(i,1,2*n){
		b[i]=a[i];
	}
	sort(b+1,b+1+2*n,[](int x,int y)->bool {
		return x>y;
	});
	foru(i,1,2*n){
		// cerr<<b[i]<<end
		mdd(ans,mul(f[i],b[i]));
	}

	static pair<int,int> rg[1000005];
	foru(i,1,1000000){
		rg[i]={INT_MAX,INT_MIN};
	}
	foru(l,1,2*n){
		int r=l;
		while(r+1<=2*n && b[r+1]==b[l]){
			r++;
		}
		// cerr<<b[l]<<' '<<l<<' '<<r<<endl;
		rg[b[l]]={l,r};
		l=r;
	}

	auto PUSH=[&ans](int x,int rk)->void {
		assert(rg[x].fi==INT_MAX || rg[x].fi-1==rk || rg[x].se+1==rk);
		mdd(ans,mul(f[rk],x));
		chkmax(rg[x].se,rk);
		chkmin(rg[x].fi,rk);
	};
	auto POP=[&ans](int x,bool L)->void {
		assert(rg[x].fi!=INT_MAX);
		if(L){
			mmv(ans,mul(f[rg[x].fi],x));
			rg[x].fi++;
		}else{
			mmv(ans,mul(f[rg[x].se],x));
			rg[x].se--;
		}
		if(rg[x].fi>rg[x].se)	rg[x]={INT_MAX,INT_MIN};
	};
	auto ADD=[&](int x)->void {
		// cerr<<"ADD "<<rg[x].fi<<' '<<rg[x].se<<endl;
		assert(rg[x+1].se==INT_MIN || rg[x+1].se+1==rg[x].fi);
		assert(rg[x].fi!=INT_MAX);
		PUSH(x+1,rg[x].fi);
		POP(x,true);
	};
	auto RMV=[&](int x)->void {
		// cerr<<"RMV "<<rg[x].fi<<' '<<rg[x].se<<endl;
		PUSH(x-1,rg[x].se);
		POP(x,false);
	};

	auto out=[]()->void {
		cerr<<"OP"<<endl;
		foru(i,1,1000000){
			if(rg[i].fi==INT_MAX)	continue;
			cerr<<i<<' '<<rg[i].fi<<' '<<rg[i].se<<endl;
		}
	};
	// out();
	
	while(q--){
		int x=RIN,y=RIN;
		if(y>0){
			foru(i,a[x],a[x]+y-1){
				// cerr<<i<<endl;
				// assert(1<=i && i<=999999);
				ADD(i);
			}
		}
		if(y<0){
			ford(i,a[x],a[x]+y+1){
				// cerr<<i<<endl;
				// assert(2<=i && i<=1000000);
				RMV(i);
			}
			// exit(1);
		}
		a[x]+=y;
		printf("%d\n",ans);
		// out();
	}

	return ;
}
这题有几个关键的步骤
  • 提取出 aia_i，发现只需要求出 fkf_k，同时在这之后的修改也是简单的。
  • 针对第 kk 大求 fkf_k 困难，转化成最前 kk 大求 gkg_k，此时可以把序列变成 0101，只关心一个数是否属于前 kk 大，是从 n!n! 变为 2n2^n 的关键一步。
    • 实际上如果不追求进一步优化，对 fkf_k 也可以用类似的思路？kk 变为 11，所有比它大的变为 22，比他小的是 00，也可以减小枚举量。但进一步优化会很抽象，不如 0101 序列更好考虑了。
  • 在 0101 序列上运行算法，发现 0101 序列与最为关键的 cnt1cnt_1 的变化不是一一对应关系，而是多对一的关系。枚举量进一步缩小到只枚举到 cnt1cnt_1 的变化路径
  • 对困难的 max⁡(0,cnt1+ci−1)\max(0,cnt_1+c_i-1) 做转化，变为了更好考虑的 cnt1cnt_1 最小值
  • 差分，需要计算最小值为 LL 的答案，转为计算最小值 ≥L\ge L 的答案
  • 折线法进一步转化
  • 处理组合数
比赛的时候死在第二步了😰️练过这种题以后应该就好一些了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...