ABC 313

SFlyer / 2023-08-17 / 原文

D

先求出 \(1\) 和其他数的异或值，再计算。

第一种是 \(2\sim n-k+1\) 的，第二种是 \(n-k+2\sim n\) 的。

E

连续两个 \(>1\) 不会结束，其他的情况从后往前处理即可。

计算每一个 \(>1\) 的贡献是几个 \(1\)。

F

巨大妙妙题。等会更。

G

操作 \(A\) 都在 \(B\) 前面，这样答案不会重复（\(A\) 在 \(B\) 后面相当于没做）。把问题转化成求 floor sum，类欧板子套上去即可。

Ex

给 \(A\) 和 \(B\) 排序没有影响。
定义 \(C\)，\(C_i=\min(A_i,A_{i-1}),C_1=A_1,C_{N+1}=A_N\)。
\(B_i>C_i\) 即可。

考虑插入 dp。\(dp_{i,j}(i\ge j)\) 表示前 \(i\) 个 \(A\) 分成 \(j\) 段（此时 \(B\) 到了 \(i+j\)）。段数从 \(a\) 变到 \(b\) 时，\(B_{a},B_{a+1},\cdots,B_{b}\) 均要大于 \(A_{i+1}\)。

转移 \(3\) 种情况：

\(A_{i}\) 单独成段。
\(A_{i}\) 在一段左或右边。
\(A_{i}\) 连接两段。

代码很好写。

code

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 5e3+3;
const ll mod = 998244353;

int n;
int a[N],b[N];
ll dp[N][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=0; i<n; i++){
		cin>>a[i];
	}
	for (int i=0; i<n+1; i++){
		cin>>b[i];
	}
	sort(a,a+n);
	sort(b,b+1+n);
	dp[0][0]=1;
	for (int i=0; i<n; i++){
		for (int bl=0; bl<=i; bl++){
			for (int ty=0; ty<3; ty++){
				if (i+bl+1-ty>n || ty>bl){
					continue;
				}
				if (ty!=2 && b[i+bl]<a[i]){
					continue;
				}
				if (ty==0){
					(dp[i+1][bl+1]+=dp[i][bl]*1ll*(bl+1)%mod)%=mod;
				}
				if (ty==1){
					(dp[i+1][bl]+=dp[i][bl]*1ll*(2ll*bl)%mod)%=mod;
				}
				if (bl-1>=0 && ty==2){
					(dp[i+1][bl-1]+=dp[i][bl]*1ll*(bl-1)%mod)%=mod;
				}
			}
		}
	}
	cout<<dp[n][1]<<endl;
	return 0;
}

// don't waste time!!!

很像 loj 2743。收录于我的这个博客。