这是 2023.3.7 DP题单十个题的题解。
T1 Colored Subgraphs (CF1796E)
简要题意：给定一棵树，你要对树进行链剖分，必须剖成上下竖直的链，求剖后最短链的长度最大值。
最小值最大，考虑二分最后的答案，显然满足单调性，于是转换成判定性问题：
能不能用长度不小于 \(mid\) 的链剖分题目给定的树。
用 DP 来进行 check，先随意钦定一个根进行 DP，例如为 \(1\)。具体在这之后需不需要换根，如何换根稍后会讲述。
设 \(dep_u\) 表示 \(u\) 下方挂着的最短链长（包括 \(u\) 自己）。
显然叶子结点的 \(dep\) 为 \(1\)，转移时 \(dep_u=\min\limits_{v\in son_u}\left\{dep_v+1\right\}\)。
然后还需要维护一个 \(MinChild_u\) 表示 \(dep_u\) 对应的那条链的底端叶子结点编号。
叶子结点的 \(MinChild\) 为它自身，转移则跟随 \(dep\) 转移即可。
如果记当前二分的长度为 \(mid\)，那么如果 \(u\) 有两个儿子的 \(dep\) 都小于 \(mid\)，这种局面肯定是非法的。
因此我们还需要临时记录一个次小链长，如果其小于 \(mid\) 则 check 为 \(false\)。
还有一种情况，根节点的 \(dep\) 小于 \(mid\)，也是非法的。
如果我们随意钦定的 \(rt\) 已经能为 \(true\)，这自然是最好的，check 可以直接返回 \(true\)，但如果为 \(false\)，并不代表 check 为 \(false\)，有可能以其他点为根是可能为 \(true\) 的，怎么办呢？
对于使我们退出的节点 \(u\)，无非两种情况。
先看第一种：有两个 \(dep\) 小于 \(mid\) 的孩子。这种情况下，只有选择这两条链上的点做根才有可能使 check 为 \(true\)。而且并非链上的所有点都有可能，只有以最低端的叶子结点为新根时才有机会使剖分满足大于等于 \(mid\) 的限制。
可以这么想：如果我们选择这两个链上方的点为根，这两个链的结构将不会发生改变，换根无效；如果选择下方的点为根，记其为 \(rt'\)，若 \(rt'\) 能为 \(true\)，则选择之前两条链的底端叶子结点也一定为 \(true\)，换根不优。
因此我们在 return false 之前记录两个 \(FailSon\) 分别为当前的节点的最小和次小链的底端节点编号，再以这两个 \(FailSon\) 进行 dfs，如果其中有部分返回 \(true\) ，check 返回 \(true\)，如果依然全部返回 \(false\)，那么 check 也就的确为 \(false\) 了。
至此直接 二分 + check 即可，代码：
// Problem: CF1796E Colored Subgraphs
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1796E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 200005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
vector<int> e[MAXN];
int dep[MAXN],FailSon1,FailSon2,MinChild[MAXN];
int mid;
bool fg;
int rt;
bool dfs(int u,int fath){
int Minx=INT_MAX,Dinx=INT_MAX,DinChild=-1;
for(auto v:e[u]){
if(v!=fath){
if(!dfs(v,u)) return false;
if(dep[v]<Minx){
Dinx=Minx;
DinChild=MinChild[u];
Minx=dep[v];
MinChild[u]=MinChild[v];
}else if(dep[v]<Dinx){
Dinx=dep[v];
DinChild=MinChild[v];
}
}
}
dep[u]=(Minx==INT_MAX?0:Minx)+1;
if(Minx==INT_MAX) MinChild[u]=u;
if(Dinx<mid){
FailSon1=MinChild[u];
FailSon2=DinChild;
return false;
}
if(u==rt && dep[u]<mid){
FailSon1=MinChild[u];
FailSon2=DinChild;
return false;
}
return true;
}
bool check(){
rt=1;
if(dfs(rt,0)) return true;
rt=FailSon1;
int tmp=FailSon2;
if(rt!=-1) if(dfs(rt,0)) return true;
rt=tmp;
if(rt!=-1) if(dfs(rt,0)) return true;
return false;
}
signed main(){
int T=RIN;
while(T--){
int n=RIN;
for(int i=1;i<=n;i++) e[i].clear(),MinChild[i]=-1;
fg=true;
foru(i,1,n-1){
int u=RIN,v=RIN;
e[u].push_back(v);
e[v].push_back(u);
}
int l=0,r=MAXN,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(check()){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
printf("%d\n",ans);
}
return 0;
}
T2 Maximum Subarray (CF1796D)
简要题意：给定一个序列，让你选择其中的 \(k\) 个数 \(+x\)，剩下的 \(-x\)，求修改后的最大子段和。
DP。设 \(dp_{i,j}\) 表示以第 \(i\) 个数结尾，已经进行了 \(j\) 次 \(+x\) 操作的最大子段和，转移即可。
如果当前的 \(i>j\) ，则可以从 \(dp_{i-1,j}\) 进行转移，即选择把当前的 \(a_i-x\)。之所以有 \(i>j\)，是为了排除 “考虑到第五个数，已经加了十次” 这种非法的状态转移。
如果 \(j>0\)，则可以从 \(dp_{i-1,j-1}\) 进行，转移，即选择把当前的 \(a_i+x\)。显然 \(j\) 需要大于 \(0\)。
至于答案处理，在转移过程中如果 \(n-i>k-j\) 即可把 \(Ans\) 对 \(dp_{i,j}\) 取 \(\max\)。含义是如果 \(i\) 后方能放开还没进行完的加法操作就尝试更新答案。
// Problem: Maximum Subarray
// Contest: Codeforces
// URL: https://m2.codeforces.com/contest/1796/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 200005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define int LL
#define LXF int
#define RIN read_32()
#define HH printf("\n")
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
using namespace std;
char buf[1<<20],*p1,*p2;
inline int read_32(){LXF X=0,w=0;char ch=0;while(ch<'0'||ch>'9'){w|=ch=='-';ch=GC;}while(ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+(ch^48),ch=GC;return w?-X:X;}
int n,k,x;
int a[MAXN],dp[MAXN][25];
signed main(){
int T=RIN;
while(T--){
n=RIN,k=RIN,x=RIN;
foru(i,1,n){
a[i]=RIN;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j]=-INF;
}
}
int ans=-INF;
for(int i=1;i<=n;i++){
for(int j=0;j<=min(k,i);j++){
if(i-1>=j)dp[i][j]=max(dp[i-1][j]+a[i]-x,a[i]-x);
if(j>0){
dp[i][j]=max(dp[i][j],max(dp[i-1][j-1]+a[i]+x,a[i]+x));
}
if(n-i>=k-j){
ans=max(ans,dp[i][j]);
}
}
}
printf("%lld\n",max(ans,0ll));
}
return 0;
}
T3 Explosions? (CF1795E)
简要题意：给定一个长度 \(n\) 的序列 \(a\)，你可以对每个数进行若干次 \(-1\) 操作，使其变成一个严格单峰的序列，问操作数加上峰顶高度的最小值。
假设我们已经求出了 \(f_i\) 和 \(g_i\) 分别表示在不修改 \(a_i\) 的前提下，使得前\(i\) 个数严格递增 / 后\(i\) 个数严格递减的最小操作次数，那么显然：
\[Ans=\max\limits_{i=1}^{n}\left\{f_i+g_i+a_i\right\} \]又因为 \(f\) 和 \(g\) 是完全对称的，求完 \(f\) 之后把 \(a\) 翻转再跑一次就能得到 \(g\)，所以只需考虑怎么求 \(f\)。
想一下朴素 \(n^2\) 暴力 DP，当前考虑到第 \(i\) 个数，那么如果 \(a_{i-1}>a_i-1\)，\(a_{i-1}\) 就需要修改。同理，如果 \(a_{j}>a_i-(i-j)\)，\(a_{j}\) 就需要修改。一旦我们找到一个不需要修改的 \(j\)，那么在这之前的修改我们就不用考虑了，直接使用 \(f_j\) 就可以，因为没有增高的操作，且降低 \(f_j\) 又会变劣，因此 \(a_j\) 不变，同时在 \(j\) 之前的数必须小于 \(a_j\)，于是这件事的代价就是 \(f_j\)。
至于 \(j+1\) 和 \(i\) 之间的部分，他们本身的和由前缀和 \(O(1)\) 得到，修改完后的和可以使用等差数列求和公式得到，于是修改 \(j+1\sim i\) 这部分代价的计算也是 \(O(1)\) 的。注意 \(i-j\) 有可能大于 \(a_i\)，使得等差数列出现负项，这显然是错误的，因为我们最多减到 \(0\)，计算时把 \(i-j\) 对 \(a_i\) 取 \(\min\) 即可。
设 \(k=\min(i-j,a_i)\)，\(s\) 为 \(a\) 的前缀和，则转移方程为：
\[dp_i=dp_j+(s_i-s_j)-\dfrac{k\times\left[(a_i-k+1)+a_i\right]}{2} \]复杂度瓶颈是 \(j\) 的查找。回看 \(j\) 需要满足的条件式：
\[a_j\leq a_i-(i-j)\\ a_j\leq a_i-i+j\\ a_j-j\leq a_i-i \]发现 \(a_i\) 变得只和 \(i\) 有关，因此可以使用单调栈维护。
复杂度 \(O(n)\)。
// Problem: CF1795E Explosions?
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1795E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 300005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define int LL
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n,h[MAXN];
int f[MAXN],g[MAXN];
int s[MAXN];
stack<LL> st;
signed main(){
int T=RIN;
while(T--){
n=RIN;
while(!st.empty()) st.pop();
foru(i,1,n){
h[i]=RIN;
s[i]=s[i-1]+h[i];
f[i]=g[i]=0;
}
st.push(1);
for(int i=2;i<=n;i++){
while(!st.empty() && h[st.top()]-st.top()>h[i]-i) st.pop();
int j;
if(st.empty()) j=0;
else j=st.top();
st.push(i);
f[i]+=f[j];
f[i]+=s[i]-s[j];
f[i]-=min(i-j,h[i])*(h[i]+h[i]-min(i-j,h[i])+1)/2;
}
reverse(h+1,h+1+n);
foru(i,1,n){
s[i]=s[i-1]+h[i];
}
while(!st.empty()) st.pop();
st.push(1);
for(int i=2;i<=n;i++){
while(!st.empty() && h[st.top()]-st.top()>h[i]-i) st.pop();
int j;
if(st.empty()) j=0;
else j=st.top();
st.push(i);
g[i]+=g[j];
g[i]+=s[i]-s[j];
g[i]-=min(i-j,h[i])*(h[i]+h[i]-min(i-j,h[i])+1)/2;
}
reverse(g+1,g+1+n);
reverse(h+1,h+1+n);
int ans=LLONG_MAX;
for(int i=1;i<=n;i++){
ans=min(ans,f[i]+g[i]+h[i]);
}
printf("%lld\n",ans);
}
return 0;
}
T4 Moscow Gorillas (CF1793D)
对于给出的两个长度为 \(n\) 的排列 \(p\) 和 \(q\) ，请你算出有多少对 \(l\) 和 \(r\) ( $ 1 \le l \le r \le n $ ) ，满足 $ \operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r]) $。
其中，一段序列的 \(\operatorname{MEX}\) 值表示 没有在该序列中出现的最小正整数。例如，$ \operatorname{MEX}([1, 3]) = 2 \(，\) \operatorname{MEX}([5]) = 1 \(，\) \operatorname{MEX}([3, 1, 2, 6]) = 4 $。
显然 \(\operatorname{MEX}\) 的取值范围是 \(1\sim n+1\)。记其为 \(m\)，考虑从小到大枚举 \(m\)。
假设当前枚举到 \(i\)，则 \(1\sim i-1\) 的数均必须出现在 \(l\sim r\) 中，而 \(i\) 在 \(l\sim r\) 中不能出现，剩下的随意。
所以到 \(i\) 之后我们把 \(i-1\) 在两个排列里的下标加入 \(set\)，再查询最小下标和最大下标，分别记为 \(lf,rf\)，显然需满足：
\[l\leq lf\\ rf\leq r \]\(i\) 在两个排列中会有两个下标，把较小的和较大的分别记作 \(Min,Max\)，则它们划分出了三个区间，即：
\[1\sim Min-1\\ Min+1\sim Max-1\\ Max+1\sim n \]讨论，并对区间取交集，把左右端点区间长度相乘从而得到答案。\(i=1\) 的情况特殊处理即可。
代码：
// Problem: CF1793D Moscow Gorillas
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1793D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 200005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int n;
int a[MAXN],at[MAXN];
int b[MAXN],bt[MAXN];
set<LL> s;
LL get(LL l,LL r){
if(r<l) return 0;
LL w=r-l+1;
return (1+w)*w/2;
}
signed main(){
n=RIN;
foru(i,1,n){
a[i]=RIN;
at[a[i]]=i;
}
foru(i,1,n){
b[i]=RIN;
bt[b[i]]=i;
}
LL ans=get(1,min(at[1],bt[1])-1)+get(min(at[1],bt[1])+1,max(at[1],bt[1])-1)+get(max(at[1],bt[1])+1,n)+1;
for(int M=2;M<=n;M++){
s.insert(at[M-1]);
s.insert(bt[M-1]);
LL lf=min(at[M],bt[M]);
LL rf=max(at[M],bt[M]);
LL Min=*s.begin();
LL Max=*s.rbegin();
if(Max<=lf-1){
ans+=(lf-Max)*Min;
}
if(lf+1<=Min && Max<=rf-1){
ans+=(rf-Max)*(Min-lf);
}
if(Min>=rf+1){
ans+=(Min-rf)*(n+1-Max);
}
}
cout<<ans;
return 0;
}
T5 Graph Coloring (CF1792F1)
题意：给定 \(n\)，请你对一个大小为 \(n\) 的完全图的边进行红蓝染色，先给出一个定义：
- 对于一个点集 \(S\) ，称其为 “红联通” 当且仅当对于所有的 \(u,v\in S\)，都存在一条路径 \(path\)，满足：\[\forall u\in path,u\in S\\ \forall e\in path,e\ is\ red \]“蓝联通” 的定义是与 “红联通” 对称的。
求出满足以下条件的染色方案数：
- 至少有一条红边
- 至少有一条蓝边
- 对于所有 \(|S|\geq 2\) 的点集 \(S\)，它要么是红联通的，要么是蓝联通的，但不能同时满足二者。
考虑 DP。
注意区分下面的叙述细节，例如 “红联通” ”红边能联通“ 的含义不一样，请结合语境。
首先有一个性质，一个图与其补图必有一个是联通的。放在这个题里也是一样，红色部分和蓝色部分互为补图，所以必有一个联通了所有点。
还有一个性质，如果 \(S\) 是红联通的，那么它的子集也是红联通的。蓝联通同理。
由于红蓝染色之间存在双射，所以不妨钦定红色部分是那个联通的。也就是说红边联通了每一个点。
设 \(dp_i\) 表示大小为 \(i\) 的，蓝色边没有联通所有点的图的染色方案数，那么显然 \(dp_1=1\)，最后的答案等于原方案加翻转方案，再减去全红和全蓝方案，即 \(Ans=2\times dp_n-2\)。
问题是怎么递推 \(dp\)。
对于大小为 \(i\) 的图，考虑所有包含 \(1\) 的点集 \(S\)，记其大小为 \(x\)，则 \(x\in[1,n-1]\)，因为 \(1\) 号点已经确定，所以从 \(n-1\) 个点钟选择剩下 \(x-1\) 个点的方案数是 \(C_{n-1}^{x-1}\) 。
根据 \(dp\) 的定义，如果想要让这个子集产生贡献，那么它必须是红联通的，所以 \(S\) 内边的染色方案是 \(dp_x\)。
记 \(S'\) 为剩下 \(n-x\) 个点组成的集合，根据题目要求，\(S'\) 本身不能既是红联通又是蓝联通，但可以是红联通和蓝联通中的任意一个，因而染边方案数为 \(2\times dp_{n-x}\)。注意如果 \(n-x=1\) 时要特判，不用乘 \(2\)，因为单个点既是红联通又是蓝联通。
考虑完了 \(S\) 和 \(S'\) 边，在它们中间的边该如何染色呢？根据 \(dp\) 定义，只有 “红边联通了所有点” 的染色方案才会被计入，我们已经保证了 \(S\) 内部的红边能联通 \(S\) 内部的所有点， 但不确定 \(S'\) 内的红边能否联通 \(S'\) 内的所有点，因为只有当 \(S'\) 也是红联通的时候才可以，而 \(S'\) 是有可能为蓝联通的。因此我们需要把跨 \(S\) 和 \(S'\) 的所有边都染成红色，保证整个图符合 \(dp_i\) 的定义，即红边能联通所有的点。
综上，对于枚举出来的 \(S\) 大小 \(x\)，其方案数为 \(C_{n-1}^{x-1}\times dp_x\times (2-[n-x=1])\times dp_{n-x}\)。
所以转移方程：
\[dp_1=1\\ dp_i=\sum_{x=1}^{i-1}C_{n-1}^{x-1}\times dp_x \times (2-[n-x=1])\times dp_{n-x} \]如果问为什么 \(x\) 取不到 \(n\) ，可以试试怎么用 \(dp_i\) 来转移 \(dp_i\)。
代码：
// Problem: CF1792F1 Graph Coloring (easy version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1792F1
// Memory Limit: 500 MB
// Time Limit: 5500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 100005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
const LL mod=998244353;
LL ksm(LL a,LL b){
a%=mod;
LL ret=1;
while(b){
if(b&1) ret=(ret*a)%mod;
b>>=1,a=(a*a)%mod;
}
return ret;
}
int n;
LL f[MAXN];
LL C[5005][5005];
signed main(){
n=RIN;
C[0][0]=1;
foru(i,1,n){
C[i][0]=1;
foru(j,1,i){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
f[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
f[i]=(f[i]+C[i-1][j-1]*f[j]%mod*f[i-j]%mod*(j==i-1?1:2)%mod)%mod;
}
}
cout<<(f[n]*2%mod-2+mod)%mod;
return 0;
}
T6 Divisors and Table (CF1792E)
题意：
给定一张 \(n \times n\) 的表格和一个正整数 \(m = m_1 \times m_2\)，表格第 \(i\) 行第 \(j\) 列的数 \(a_{i, j} = i \times j\)。
现在需要你求出 \(m\) 的每个因子 \(d\) 是否在表格中出现，若出现，则求出其出现在表格中的最小行号。
其实不需要什么高深的技巧，直接分解 \(m\) 的所有因数，\(m\) 的值域是 \(10^{18}\)，所以因数个数是 \(10^6\) 级别的。
先在 \(m\) 的因数里二分找到起点，之后暴力枚举，找到符合条件的数之后直接退出。
// Problem: CF1792E Divisors and Table
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1792E
// Memory Limit: 250 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 100005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
vector<LL> s,s1,s2;
signed main(){
int T=RIN;
while(T--){
s.clear();
s1.clear();
s2.clear();
int n=RIN,a=RIN,b=RIN;
for(int i=1;i*i<=a;i++){
if(a%i==0){
s1.push_back(i);
s1.push_back(a/i);
}
}
for(int i=1;i*i<=b;i++){
if(b%i==0){
s2.push_back(i);
s2.push_back(b/i);
}
}
for(auto x:s1){
for(auto y:s2){
s.push_back((LL)x*(LL)y);
}
}
sort(s.begin(),s.end());
auto ptr=unique(s.begin(),s.end());
LL ans=0,cnt=0;
for(auto it=s.begin();it!=ptr;it++){
LL x=*it;
LL l=0,r=it-s.begin(),st;
while(l<=r){
LL mid=(l+r)>>1;
if(x/s[mid]<=n){
st=mid;
r=mid-1;
}else{
l=mid+1;
}
}
for(int i=st;i<s.size();i++){
if(s[i]>n) break;
if(x%s[i]==0 && x/s[i]<=n){
ans^=s[i];
cnt++;
break;
}
}
}
cout<<cnt<<' '<<ans<<endl;
}
return 0;
}
T7 Serval and Music Game (CF1789E)
题意：
给定整数 \(n\) 和长度为 \(n\) 的递增序列 \(s\)。
定义 \(f(x)\) 为满足下列要求的整数 \(i(1\leq i\leq n)\) 的数量：
- 存在非负整数 \(p_i,q_i\) 使得 \(s_i=p_i\bigg\lfloor\dfrac{s_n}{x}\bigg\rfloor+q_i\bigg\lceil\dfrac{s_n}{x}\bigg\rceil\)。
你需要求出 \(\sum_{x=1}^{s_n}x\times f(x)\) 对 \(998244353\) 取模后的值。
从 \(1\sim s_n\) 枚举一个 \(x\)
如果 \(x\) 是 \(s_n\) 的因数，直接做，复杂度是调和级数的。
如果 \(x\) 不是 \(s_n\) 的因数，则原式：
\[s_i=p_i\lfloor\dfrac{s_n}{x}\rfloor+q_i\lceil\dfrac{s_n}{x}\rceil\\ =p_i\lfloor\dfrac{s_n}{x}\rfloor+q_i\left(\lfloor\dfrac{s_n}{x}\rfloor+1\right)\\ =p_i\lfloor\dfrac{s_n}{x}\rfloor+q_i\lfloor\dfrac{s_n}{x}\rfloor+q_i\\ =\left(p_i+q_i\right)\lfloor\dfrac{s_n}{x}\rfloor+q_i \]设 \(k=\lfloor\dfrac{s_n}{x}\rfloor\)，则：
\[s_i=(p_i+q_i)k+q_i \]如果想要 \(p_i,q_i \geq 0\)，则 \(q_i\leq p_i+q_i\)
显然 \(p_i+q_i\) 尽可能大，\(q_i\) 尽可能小是不劣的。
于是把这个式子看做 “被除数=商*除数+余数" 的形式
则 \(p_i,q_i\) 对应商，\(k\) 对应除数，\(q_i\) 对应余数。
于是有：
\[s_i \bmod k \leq \lfloor\dfrac{s_i}{k}\rfloor \]由此式子还能知道当 \(s_i \geq k^2\) 时原式一定成立，因为余数 \(q_i\) 一定小于除数 \(k\)，而商 \(p_i+q_i\) 一定不小于除数 \(k\)，故 \(q_i \leq p_i+q_i\) 恒成立。
直接按照区间查贡献即可，加上整除分块的优化即可通过，原理就是在整除意义下 \(x\) 改变时 \(k\) 不一定改变。
// Problem: CF1789E Serval and Music Game
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1789E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define INF 0x7fffffff
#define MAXN 1000005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
using namespace std;
inline LXF rin(){
LXF x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*w;
}
int a[MAXN];
int vis[10000003],cnt[10000003];
const LL mod=998244353;
signed main(){
int T=RIN;
for(int tm=1;tm<=T;tm++){
int n=RIN;
LL ans=0;
foru(i,1,n){
a[i]=RIN;
vis[a[i]]=tm;
}
foru(i,1,a[n]){
cnt[i]=cnt[i-1]+(vis[i]==tm);
}
LL last=0;
for(int x=1;x<=a[n];x++){
LL tot=0;
LL A=a[n]/x;
if(x!=1 && a[n]%x!=0 && a[n]%(x-1)!=0 && (LL)(a[n]/x)==(LL)(a[n]/(x-1))){
tot=last;
}else{
if(a[n]%x==0){
for(int i=1;(LL)i*A<=a[n];i++){
if(vis[i*A]==tm){
tot++;
}
}
}else{
for(int j=1;j<A && j*A<=a[n];j++){
tot=(tot+(cnt[min((LL)j*A+j,(LL)a[n])]-cnt[(LL)j*A-1])%mod)%mod;
}
if(A*A<=a[n]) tot=(tot+(cnt[a[n]]-cnt[A*A-1])%mod)%mod;
}
}
last=tot;
ans=(ans+(LL)tot*x%mod)%mod;
}
printf("%lld\n",ans);
}
return 0;
}