20230823 B 组模拟赛 题解
前言
之前集训的时候好久没写题解了，感觉有点退步。
题面 压缩包密码是 CW 通用密码，大小写敏感。
T1
这次 T1 挺简单的，但挺有意思。
第一问很简单，发现最优是三个分一组，最后剩下的分情况讨论一下就行了，不多赘述。
重点在第二问，考虑期望 DP，设 $dp_i$ 表示当 $n$ 变为 $i$ 时，$k$ 的期望值。易得转移方程：
$$dp_i=\sum_{j=i+1}^n\dfrac{dp_j\times (j-i)}{j}$$
边界是 $dp_{n}=1$，答案就是 $dp_0$。
这样直接做显然是过不了的，考虑优化。
显然可以把式子中的 $i,j$ 拆开，那么式子就能化成这样：
$$ \begin{aligned} dp_i&=\left(\sum_{j=i+1}^n dp_j\times\dfrac{j}{j}\right)-\left(\sum_{j=i+1}^n dp_j\times\dfrac{i}{j}\right)\\ &=\left(\sum_{j=i+1}^n dp_j\right)-i\left(\sum_{j=i+1}^ndp_j\times\dfrac{1}{j}\right) \end{aligned} $$
然后就很明了了，随便维护一下 $\sum dp_j$ 和 $\sum dp_j\times\frac{1}{j}$ 就行了。
因为状态数是 $O(n)$ 的，转移是 $O(\log n)$ 的（因为要算逆元），复杂度是 $O(n\log n)$
参考代码
#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=5e5+5,inf=0x3f3f3f3f;
int n,mod,dp[N],nw,sv;
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
signed main(){
freopen("mit.in","r",stdin);
freopen("mit.out","w",stdout);
n=read();mod=read();
if(n%3==1){
printf("%lld\n",1ll*ksm(3,n/3-1)*4%mod);
}else if(n%3==2){
printf("%lld\n",1ll*ksm(3,n/3)*2%mod);
}else{
printf("%d\n",ksm(3,n/3));
}
dp[n]=1;
nw=ksm(n,mod-2);sv=1;
fordown(i,n-1,1){
dp[i]=(sv+mod-1ll*nw*i%mod)%mod;
int inv=ksm(i,mod-2);
(nw+=1ll*dp[i]*inv%mod)%=mod;
(sv+=dp[i])%=mod;
}
dp[0]=sv;
printf("%d\n",dp[0]);
}
T2
这道题赛时没想出来，感觉做法挺有参考价值的。
首先假如没有上下界限制应该怎么做（即特殊性质 $1$）。
这就非常典了。假如在 DP 中计入用了哪些数那么状态数将达到指数级别。发现其实我们其实只关心数的相对大小关系，那么可以定义 $dp_{i,j}$ 表示 $i$ 阶排列有 $j$ 个前缀最大值的方案数。转移就考虑在哪两个数之间插入一个数。相当于比它小的数不变，比它大的整体加一，然后把它插在排列末尾，那么转移方程就很显然：
$$dp_{i,j}=dp_{i-1,j}\times(i-1)+dp_{i-1,j-1}$$
注意判断一下边界。然后就可以得 40pts 啦。
然后考虑怎么解决上下界问题。首先区间问题转化为前缀问题，转化成字典序必须小于 $b$ 的方案数减去 必须小于 $a$ 的方案数加上特判 $b$ 自己是否合法，然后再考虑咋做。
这种字典序比较的题可以考虑类似于数位 DP 的思路，就是考虑前面卡到上界，后面能怎么填。
假设我们的字典序必须比排列 $s$ 小。
考虑前面 $i-1$ 位都卡到上界，且前面最大值为 $mx$，前面有 $nw$ 个前缀最大值，后面有多少种填法。
首先假如 $nw>k$，肯定只有 $0$ 种填法。因为你总不可能让前缀最大值数量变小吧？
然后考虑这一位填 $j(1 \le j < s_i)$ 后面的分 $j>mx,j<mx$ 两种情况的填法。
首先 $j<mx$，这一位本身不会有贡献，且后面小于 $mx$ 的也肯定不会有贡献，那么后面需要的前缀最大值个数就是 $k-nw$，且后面有 $n-mx$ 个可能做贡献，也就是说后面 $(mx,n]$ 这些数的相对位置有 $dp_{n-mx,k-nw}$ 种。
然后考虑不会做贡献的可以随意排列，有 $(mx-i)!$ 种，然后 $(mx,n]$ 这些数的位置有 $\binom{n-i}{n-mx}$ 种，故总填法为：
$$dp_{n-mx,k-nw}\times(mx-i)!\times\dbinom{n-i}{n-mx}$$
然后从前往后扫一遍维护 $mx,nw$ 的值即可，注意不要用到重复的数。
而 $j>mx$ 的情况其实差不多，不同点在于 $j$ 会产生一点贡献以及 $mx$ 变成了 $j$，特判一下就行了。
状态数为 $O(n^2)$，转移是 $O(1)$ 的（预处理阶乘与组合数），总复杂度 $O(n^2)$。
参考代码
#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=3005,inf=0x3f3f3f3f,mod=998244353;
int n,m,a[N],b[N];
int dp[N][N],vis[N],ans;
int fact[N],inv[N],finv[N];
int C(int n,int m){
if(n<m) return 0;
return 1ll*fact[n]*finv[m]%mod*finv[n-m]%mod;
}
int gans(int* s){
mem(vis,0);
int nw=0,mx=0,res=0;
forup(i,1,n){
if(nw>m) break;
if(n-mx<m-nw) break;
forup(j,1,s[i]-1){
if(vis[j]) continue;
int p=(j>mx);
if(p+nw>m) break;
if(n-max(j,mx)<m-nw-p) break;
(res+=1ll*dp[n-max(j,mx)][m-nw-p]*C(n-i,n-max(j,mx))%mod*fact[max(j,mx)-i]%mod)%=mod;
}
if(s[i]>mx) mx=s[i],++nw;
vis[s[i]]=1;
}
return res;
}
signed main(){
freopen("fail.in","r",stdin);
freopen("fail.out","w",stdout);
n=read();m=read();
forup(i,1,n){
a[i]=read();
}
forup(i,1,n){
b[i]=read();
}
fact[0]=fact[1]=inv[1]=finv[0]=finv[1]=1;
forup(i,2,n){
fact[i]=1ll*fact[i-1]*i%mod;
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
finv[i]=1ll*finv[i-1]*inv[i]%mod;
}
dp[0][0]=dp[1][1]=1;
forup(i,2,n){
forup(j,1,min(i,m)){
if(j>1){
(dp[i][j]+=dp[i-1][j-1])%=mod;
}
(dp[i][j]+=1ll*dp[i-1][j]*(i-1)%mod)%=mod;
}
}
ans=(gans(b)+mod-gans(a))%mod;
int mx=0,cnt=0;
forup(i,1,n){
if(b[i]>mx){
mx=b[i];++cnt;
}
}
if(cnt==m) ans++;ans%=mod;
printf("%d\n",ans);
}
T3
首先有个结论能让这道看起来不可做的题变成可做题：
假如你要把一个序列切成 $k$ 段，每切一刀的代价是切成的两段分别的总和相乘，那么总代价就是整个序列总和的平方减去最后每一段总和的平方最后除以二。
很好证明，首先容易发现无论切的顺序如何，只要 $i,j$ 不在同一段，那么它们就会产生 $a_i\times a_j$ 的贡献。可以自己分情况讨论一下，在此略过。那么这个结论就很显然了，比较基础的容斥。
然后由于最后一定要切成 $n$ 段，所以第一部分的和就是 $(\sum a_i)^2-(\sum a_i^2)$。那么我们只用管 $h=1$ 时的 $w$ 了。
这时这个问题就转化成了把序列分成 $k$ 段，每段的权值是那坨式子，最小化权值和。
容易想到 DP，设 $dp_{i,j}$ 表示考虑前 $j$ 个，分了 $i$ 段的最小权值和。那么有个显然的转移方程：
$$dp_{i,j}=\min_{l=1}^{j-1}dp_{i-1,l}+w(l+1,j)$$
其中 $w(l,r)$ 表示区间 $[l,r]$ 的权值。由于 $q$ 可以倒序遍历 $l$ 时求出，$\sum_{i=l+1,r}\left|a_i-a_{i-1}\right|+(a_i\oplus a_{i-1})$ 可以前缀和维护，所以可以 $O(n^2k)$ 获得 67pts 的好成绩。
考虑如何优化。这种式子我们一般猜它有决策单调性（即 $w(l,r)$ 满足四边形不等式）来优化，那么 $w(l,r)=\left(\sum_{i=l+1}^r\left|a_i-a_{i-1}\right|+(a_i\oplus a_{i-1})\right)q(l,r)$ 满不满足四边形不等式呢？答案是满足。
首先看 $q(l,r)$，这个非常经典，在 CF833B The Bakery 里面就是这个式子满足四边形不等式。
具体来说，我们要证 $q(a,d)+q(b,c)\ge q(a,c)+q(b,d)(a < b < c < d)$，首先容易发现其实 $q$ 就是区间内相等的数的对数乘以二加上区间长度（考虑乘法原理），那么考虑相等的数对 $a_i,a_j(i<j)$ 的位置，分几种情况讨论：
- $b \le i,j \le c$：对不等号两侧都产生 $2$ 的贡献。
- $a\le i,j \le b\;\vee\;c\le i,j\le d$：对不等号两侧都产生 $1$ 的贡献。
- $a\le i \le b < j \le c \; \vee\;b\le i <c \le j\le d$：对不等号两侧都产生 $1$ 的贡献。
- $a\le i < b <c < j \le d$：对不等号左侧产生 $1$ 的贡献。
而区间长度之和相等，故 $q(l,r)$ 满足四边形不等式。
然后剩下的那一坨我们不管内容是什么，设 $x=\left(\sum_{i=a+1}^b\left|a_i-a_{i-1}\right|+(a_i\oplus a_{i-1})\right),y=\left(\sum_{i=b+1}^c\cdots\right),z=\left(\sum_{i=c+1}^d\cdots\right)$，那么 $w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$ 可以化成这样：
$$q(a,d)(x+y+z)+q(b,c)y\ge q(a,c)(x+y)+q(b,d)(y+z)$$
而左边可以这样化：
$$ \begin{aligned} &q(a,d)(x+y+z)+q(b,c)y\\ = &q(a,d)(x+z)+y(q(b,c)+q(a,d))\\ \ge&q(a,c)x+q(b,y)z+y(q(a,c)+q(b,d))\\ = &q(a,c)(x+y)+q(b,d)(y+z) \end{aligned} $$
那么不等号成立。所以 $w(l,r)$ 满足四边形不等式。
接下来是经典证明，四边形不等式推结论单调性。因为我以前没证过所以这里写一下：
设 $dp_{i,j}$ 的最优决策点为 $l_1$（即 $\forall l'\ne l_1,dp_{i-1,l'}+w(l'+1,j)\ge dp_{i-1,l_1}+w(l_1+1,j)$），$dp_{i,j+1}$ 的最优决策点为 $l_2$（同理），那么我们就要证 $l_1\le l_2$。不妨假设 $l_1>l_2$，那么有:
$$ dp_{i-1,l_2}+w(l_2+1,j)\ge dp_{i-1,l_1}+w(l_1+1,j)\\ dp_{i-1,l_1}+w(l_1+1,j+1)\ge dp_{i-1,l_2}+w(l_2+1,j+1) $$
不等式具有同向可加性，两式相加，可得：
$$w(l_2+1,j)+w(l_1+1,j+1)\ge w(l_1+1,j)+w(l_2+1,j+1)$$
由于 $l_1>l_2$，故上式与四边形不等式矛盾。故 $l_1$ 必定小于等于 $l_2$。
有了四边形不等式就可以直接分治了。另外 $q(l,r)$ 直接求不是很好处理，我们可以考虑类似莫队用双指针解决，如果推平分治那每一层就是 $O(n)$ 的。
复杂度 $O(kn\log n)$
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 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 i64 N=6e4+5,inf=1e18;
i64 n,k,h,a[N],ans,sum;
i64 dp[45][N];
struct Node{
i64 L,R,l,r;
};
queue<Node> q;
i64 cnt[N],cst,pre[N];
void add(i64 i){
cst-=cnt[a[i]]*cnt[a[i]];
cnt[a[i]]++;
cst+=cnt[a[i]]*cnt[a[i]];
}
void del(i64 i){
cst-=cnt[a[i]]*cnt[a[i]];
cnt[a[i]]--;
cst+=cnt[a[i]]*cnt[a[i]];
}
i64 ll=1,rr=0;
i64 calc(i64 L,i64 R){
while(rr<R) add(++rr);
while(ll>L) add(--ll);
while(rr>R) del(rr--);
while(ll<L) del(ll++);
return cst*(pre[R]-pre[L]);
}
signed main(){
freopen("on.in","r",stdin);
freopen("on.out","w",stdout);
n=read();k=read();h=read();
forup(i,1,n){
a[i]=read();
ans-=a[i]*a[i];
sum+=a[i];
pre[i]=pre[i-1]+abs(a[i]-a[i-1])+(a[i]^a[i-1]);
}
ans+=sum*sum;
ans>>=1;
if(h==0){
printf("%lld\n",ans);
return 0;
}
forup(i,1,n){
add(i);
dp[1][i]=cst*(pre[i]-pre[1]);
}
dp[1][0]=inf;
mem(cnt,0);cst=0;
ll=1;rr=0;
forup(t,2,k){
dp[t][0]=inf;
while(q.size()) q.pop();
q.push(Node{t,n,t-1,n-1});
while(q.size()){
i64 L=q.front().L,R=q.front().R,l=q.front().l,r=q.front().r;
q.pop();
if(L>R) continue;
if(l==r){
forup(i,L,R){
dp[t][i]=dp[t-1][l]+calc(l+1,i);
}
continue;
}
i64 mid=(L+R)>>1,bst=-1;
dp[t][mid]=inf;
forup(i,l,min(mid-1,r)){
del(ll++);
if(dp[t-1][i]+calc(i+1,mid)<dp[t][mid]){
bst=i;
dp[t][mid]=dp[t-1][i]+calc(i+1,mid);
}
}
q.push(Node{L,mid-1,l,bst});q.push(Node{mid+1,R,bst,r});
}
}
printf("%lld\n",dp[k][n]+ans);
}