20230913 B 组模拟赛 题解
前言
T2 暴力写挂，T4 分讨少考虑一种情况，怒挂 115pts，估分 50+15+30+100=195，实际得分 50+0+40+0=90。大家看个乐子就好
这次题个人难度排序 $T4<T1<T2<T3$
T1
首先容易发现合法的情况是很难统计的，但是总序列数很好统计，不妨用容斥处理。
那么容易得出答案即为：
$$\sum_{S\subseteq[1,n]}f(S)(-1)^{|S|}$$
其中 $S$ 是表示钦定不合法的位置的集合（其他位置不管），不合法位置，即使得 $l_{i-1}=kl_{i}(k\in N^{*})$ 的 $i$ 的数量。$f(S)$ 表示满足 $S$ 集合中的位置均不合法的序列数量。
容斥比较典，就不细讲了。
容易发现容斥系数只和集合大小的奇偶性有关，那么设 $dp_{i,0/1}$ 表示考虑前 $i$ 个数，$|S|$ 为偶数/奇数的序列数量。
但是假如不合法位置都是独立的应该很好转移，可惜它不一定是。
但是倍数这个东西其实是很神奇的，假如有一段连续不合法的段 $b_1,b_2\dots b_t$，容易发现 $b_{i+1}\le\frac{1}{2}b_i$，那么连续不合法段的长度就是 $\log m$ 级别的了。
也就是说我们可以预处理长度为 $l\in[1,\left\lceil\log m\right\rceil]$ 的不合法段的数量，这个可以设 $f_{i,j}$ 表示长度为 $i$，结尾为 $j$ 的连续不合法段方案，转移枚举上一个数是什么即可，复杂度是调和级数乘以 $\log m$ 等于 $O(m\log^2 m)$。
然后原来 DP 的转移就枚举最后一段的长度即可，注意我们钦定枚举的这一段前一个位置合法，不然在枚举更长的方案时会算重，而我们的容斥又处理不了这个。
预处理复杂度 $O(m\log^2m)$，DP 统计复杂度 $O(n\log m)$，可以通过。
听说这道题有线性递推做法，$n$ 可以开到很大， 但是某位先哲曾经说过，能通过的就是正解 。
/// details | 参考代码 open: False type; success
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,m,dp[N][2],f[25][N],ff[25],sum;
void adm(int &a,int b){
a+=b;
if(a>mod) a-=mod;
}
void dlm(int &a,int b){
a-=b;
if(a<0) a+=mod;
}
signed main(){
n=read();m=read();
forup(i,1,m){
f[0][i]=1;
}
ff[0]=0;
forup(i,1,20){
forup(j,1,m){
for(int k=j*2;k<=m;k+=j){
adm(f[i][j],f[i-1][k]);
}
adm(ff[i],f[i][j]);
}
}
dp[0][0]=1;
forup(i,1,n){
dp[i][0]=1ll*dp[i-1][0]*m%mod;
dp[i][1]=1ll*dp[i-1][1]*m%mod;
forup(j,1,min(20,i)){
adm(dp[i][0],1ll*dp[i-j-1][j&1]*ff[j]%mod);
adm(dp[i][1],1ll*dp[i-j-1][(j&1)^1]*ff[j]%mod);
}
}
dlm(dp[n][0],dp[n][1]);
printf("%d\n",dp[n][0]);
}
///
T2
构造题。
首先考虑题目给的要求是什么意思，先不考虑起始只能是 $1$，那么就是要构造一个序列，使得前面一段是一条链，中间分界点后后面相邻两点没有连边。
那么我们可以考虑在分界点处构造。
具体来说，从小到大考虑每个点能放在分界点的哪一侧，然后维护新的分界点。
再具体点，设分界点为 $x$，左侧为 $a$，右侧为 $b$，新加入的点为 $i$，若 $i-x$ 的连边情况和 $a-x$ 相同，就插入分界点右侧，反之插入左侧。
这个有很多种维护方式，我是用栈维护左侧和右侧。
但是栈维护会有一个问题，就是 $1$ 被拉出栈底（考虑分界点的转移，是可能出现这种情况的），那么 $1$ 就不是开头了。解决办法很暴力，当 $1$ 被拉出栈底说明那个栈空了，不妨设这是左侧栈，那么直接把所有元素重新倒进左侧栈即可。考虑假如当前左侧栈有 $x$ 个元素，右侧栈空，那么把栈底拉出来至少需要再加 $x$ 个元素（可能会有一点常数区别，但是无所谓了），那么元素量就会翻倍，所以至多倒 $\log n$，复杂度 $O(n\log n)$。
结果貌似因为常数问题（或者因为没卡这个做法）比那些用链表的 $O(n)$ 哥还快。
/// open: False type: success
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f;
int n,m,p,p2;
set<pii> es;
stack<int> s1,s2;
int x;
vector<int> ans;
bool chk(int a,int b){
if(a>b) swap(a,b);
return es.count(mkp(a,b));
}
signed main(){
n=read();m=read();
forup(i,1,m){
int u=read(),v=read();
if(u>v) swap(u,v);
es.insert(mkp(u,v));
}
x=1;
forup(i,2,n){
if(i==p) continue;
if(s1.empty()||!(chk(x,i)^chk(s1.top(),x))){
s1.push(x);
if(s2.size()&&!(chk(x,i)^chk(i,s2.top()))){
s1.push(i);
x=s2.top();s2.pop();
}else{
x=i;
}
}else{
s2.push(x);
if(s1.size()&&!(chk(x,i)^chk(i,s1.top()))){
s2.push(i);
x=s1.top();s1.pop();
if(s1.empty()){
s1.push(x);
while(s2.size()>1){
s1.push(s2.top());
s2.pop();
}
x=s2.top();s2.pop();
}
}else{
x=i;
}
}
}
s2.push(x);
while(s1.size()){
s2.push(s1.top());
s1.pop();
}
while(s2.size()){
ans.push_back(s2.top());
s2.pop();
}
for(auto i:ans){
printf("%d ",i);
}
}
///
T3
本场考试最难题。
首先考虑题意转化，容易发现原来的 $a$ 是不重要的，如果我们只关心差分数组 $a'$，那么问题就变成了有标号地选 $n$ 个数，总和小于等于 $m$，求前 $\forall k\in[1,n]$ 小的总和。
容易（存疑）想到 DP，设 $dp_{i,j,k}$ 表示分 $i$ 段，总和小于等于 $j$，前 $k$ 小总和的期望。那么考虑转移。
这个转移超级神奇，考虑现在有一些段长度为 $1$，那么假如所有段长度全部减一，这些就会变成 $0$，它们显然是最小的，那么后面其余的就是一个子问题，若有 $x$ 段等于 $1$，那么剩余的就是一个 $i'=i-x,j'=j-i$ 的子问题。
那么就能转移了：
$$dp_{i,j,k}=\dfrac{\sum_{x=0}^k\dbinom{i}{x}\dbinom{j-i}{i-x}dp_{i-x,j-i,k-x}}{\dbinom{j}{i}}+k$$
解释一下转移方程：
首先是 $\sum$ 的上下界，最小没有一个为 $1$，当 $x>k$ 时，根据定义容易发现贡献为 $0$，可以跳过。然后 $\binom{i}{x}$ 表示从 $i$ 个里面选 $x$ 个为 $1$。后面的 $\binom{j-i}{i-x}dp_{i-x,j-i,k-x}$ 是把前面状态 $dp_{i-x,j-i,k-x}$ 的期望转化成贡献，组合数为什么是这个我们暂且按下不表。然后期望等于贡献乘以概率，这就是分母的意思。然后后面加上 $k$ ，因为对于第 $k$ 段，前面总共减去了 $k$，后面期望再任何情况下都会加上这 $k$ 个。
关于组合数，我们是把小于等于 $j$ 个数分成 $i$ 段，那么相当于把 $j$ 个无标号小球放进 $i+1$ 个有标号盒子里，其中最后一个盒子可以为空，其余不能为空，插板法解决，注意最后一个小球后面也能插板，两个组合数均这样考虑。
然后初始值为 $dp_{i,i,j}=j$，显然。
复杂度 $O(n^3m)$，注意精度问题，比如组合数可以递推预处理。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=55,M=1e4+5,inf=0x3f3f3f3f;
int n,m;
double C[M][N],dp[N][M][N];
signed main(){
n=read();m=read();
C[0][0]=1;
forup(i,1,m){
C[i][0]=1;
forup(j,1,min(i,n)){
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
forup(i,1,n){
forup(j,1,i){
dp[i][i][j]=j;
}
forup(j,i+1,m){
forup(k,1,i){
forup(x,0,k){
dp[i][j][k]+=C[j-i][i-x]*C[i][x]*dp[i-x][j-i][k-x];
}
dp[i][j][k]=dp[i][j][k]/C[j][i]+k;
}
}
}
forup(i,1,n){
printf("%.7lf ",dp[n][m][i]);
}
}
T4
全场最简单题，赛时分类讨论少一种情况 100->0。我曾在午休时发下豪言壮语说我下午十分钟之内改出来。结果就是如果我改不出来我是小丑，如果改出来了说明挂大分我是超级小丑。事实证明我是三倍超级小丑，因为三分钟就改出来了。
看到异或就要想到 01trie，那么我们先把 $a_i$ 塞进 01trie 里面再考虑。
在二进制下考虑。
首先对于 $k$ 的前导 $0$，我们所选集合内对应的位置必须完全相同，在 01trie 下表现为只能走一条路，两种情况取 $\max$。
然后考虑第一个 $1$，这一位全选相同的就必定小于 $k$ 了（情况 $1,2$），那么考虑分出两个指针 $u,v$，分别走两路，首先 $u,v$ 各自子树内部可以随意选，只需考虑 $u,v$ 子树互相的影响即可（情况 $3$），三种情况取 $\max$。
对于情况 $3$，我们继续往下搜索，仍然分 $k$ 这一位为 $0,1$ 考虑。
如果是 $0$，$u,v$ 只能走同一边，取 $\max$。
如果是 $1$，那么假如 $u,v$ 走同一条路直接合法了（情况 $1，2$），然后假如 $u$ 走 $0$，$v$ 走 $1$，那么就是一个子问题，但容易发现此时 $v$ 走 $0$ 的所有数均可以加入集合，$u$ 走 $1$ 的也是同理（情况 $3,4$），然后 $u\to 1,v\to 0$ 的同理（情况 $5,6$），以及最后一种情况，即分两路考虑，容易法案 $u\to 0,v\to 1$ 和 $u\to 1,v\to 0$ 是可以共存的（情况 $7$），直接全取 $\max$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int t,n,m,a[N];
int son[N*25][2],sum[N*25],cnte;
void init(){
forup(i,0,cnte) son[i][0]=son[i][1]=sum[i]=0;
cnte=0;
}
void Insert(int a){
int p=0;
fordown(i,20,0){
int c=(a>>i)&1;
if(!son[p][c]) son[p][c]=++cnte;
p=son[p][c];
sum[p]++;
}
}
int work(int u,int v,int q){
if(!u||!v){
if(u) return sum[u];
else return sum[v];
}
if(q==-1) return sum[u]+sum[v];
if(m&(1<<q)){
int res1=work(son[u][0],son[v][1],q-1),res2=work(son[u][1],son[v][0],q-1);
return max({
sum[son[u][0]]+sum[son[v][0]],sum[son[u][1]]+sum[son[v][1]],
res1+sum[son[v][0]],res2+sum[son[v][1]],
res1+sum[son[u][1]],res2+sum[son[u][0]],
res1+res2
});
}else{
return max(work(son[u][0],son[v][0],q-1),work(son[u][1],son[v][1],q-1));
}
}
int solve(int p,int q){
if(!p&&q!=20) return 0;
if(q==-1) return sum[p];
if(m&(1<<q)){
return max({sum[son[p][0]],sum[son[p][1]],work(son[p][0],son[p][1],q-1)});
}else{
return max(solve(son[p][0],q-1),solve(son[p][1],q-1));
}
}
signed main(){
t=read();
while(t--){
init();
n=read();m=read();
forup(i,1,n){
a[i]=read();
Insert(a[i]);
}
printf("%d\n",solve(0,20));
}
}