2026 NOI 做题记录（十五）
\(\text{By DaiRuiChen007}\)
A. [UOJ702] 张飞卷精兵 (3.5)
比赛过程看成树，从大到小填树，限制就是父子拓扑序，每次优先填系数为 \(-1\) 的层，如果无法填则选择儿子最多（胜利次数最多）的点。
写成代码后容易优化复杂度。
时间复杂度 \(\mathcal O(n\log P)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5,MOD=998244353,Q=MOD-1;
ll ksm(ll a,ll b,ll p=MOD) { ll s=1; for(;b;a=a*a%p,b>>=1) if(b&1) s=s*a%p; return s; }
ll ans=0,m;
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n; cin>>n,m=ksm(2,n,Q);
for(int i=n;~i;--i) {
ll c=(i==n);
if(i<=n-2) c=ksm(2,n-2-i,Q);
int t=(m+(Q-1-i)*c)%Q;
ans=(ans+(ksm(2,m)+MOD-ksm(2,t))*ksm(ksm(2,i+1)-1,MOD-2))%MOD,m=t;
}
cout<<ans<<"\n";
return 0;
}
B. [UOJ703] 赵云八卦阵 (4.5)
dp 维护末尾元素在线性基中的排名，按照加入 \(a_i\) 是否改变前缀线性基讨论，如果线性基不变，则结尾元素只会在线性基中排名 \(+1\)，容易简单维护，如果加入 \(a_i\) 导致线性基变化，则快速维护其排名变化。
另一个更优的做法是取出所有被插入线性基的元素 \(b_1\sim b_m\)，如果 \(b_i\) 在答案中，则 \([b_i,n]\) 都在答案中，因此状态只要记录 \([b_i,n]\) 中有 \(j\) 个 \(b\) 元素和所有非 \(b\) 元素时最大的开头元素。
时间复杂度 \(\mathcal O(n\log V)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5;
struct LB {
ll b[64];
bool ins(ll x) {
for(int i=59;~i;--i) if(x>>i&1) {
if(!b[i]) {
for(int j=i-1;~j;--j) if(x>>j&1) x^=b[j];
b[i]=x;
for(int j=i+1;j<60;++j) if(b[j]>>i&1) b[j]^=x;
return 1;
} else x^=b[i];
}
return 0;
}
ll rnk(ll x) {
ll k=0,z=0;
for(int i=59;~i;--i) if(b[i]) {
k<<=1;
if((z^b[i])<x) k|=1,z^=b[i];
}
return k;
}
ll val(ll k) {
ll x=0;
for(int i=0;i<60;++i) if(b[i]) {
x^=(k&1?b[i]:0),k>>=1;
}
return x;
}
ll pre(ll x,ll w) {
for(int i=59;~i;--i) x=min(x,x^b[i]);
if(x>=w) return -1;
for(int i=59;~i;--i) if((x^b[i])<w) x^=b[i];
return x;
}
} B[64];
int n,m,p[64];
ll a[MAXN],f[64];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i) if(B[m+1].ins(a[i])) p[m++]=i,B[m+1]=B[m];
p[m]=n+1,f[0]=1ll<<60,fill(f+1,f+m+1,-1);
ll z=0,s=0;
for(int i=m-1;~i;--i) {
ll c=p[i+1]-p[i]-1;
if(c) {
for(int j=0;j<=m-i;++j) if(f[j]>0) {
ll t=B[i+1].rnk(f[j]);
z=max(z,j+s+min(c,t+1));
if(t>=c) f[j]=B[i+1].val(t-c+1);
else f[j]=-1;
}
s+=c;
}
for(int j=m-i;~j;--j) if(~f[j]) f[j+1]=max(f[j+1],B[i].pre(a[p[i]],f[j]));
}
for(int i=0;i<=m;++i) if(~f[i]) z=max(z,s+i);
cout<<z<<"\n";
return 0;
}
C. [UOJ704] 马超战潼关 (5)
对残量网络缩点，变成计数包含 \(S\) 的导出子图数量。
直接爆搜复杂度 \(\mathcal O(2^{2n})\)，如果记忆化搜索，注意到只关心未搜索的覆盖情况，因此前 \(n\) 个点有 \(2^n\) 种不同的集合，后 \(n\) 个点中只会记忆化 \(2^n\) 种方案，复杂度 \(\mathcal O(n2^n)\)。
对于非匹配点一定是 \(S\) 后继或 \(T\) 前驱，不用关心。
而匹配点的右端点仅有唯一出边，所以把匹配的两个端点同时决策，只会对后续集合产生两种本质不同的贡献，即是否有选点，点数降为 \(n\) 个。
时间复杂度 \(\mathcal O(n2^{n/2})\)。
代码：
#include<bits/stdc++.h>
#define ull unsigned long long
#define LL __int128
using namespace std;
struct Edge { int v,f,e; } G[2005];
int S,T,ec=1,hd[105],cur[105],d[105];
void link(int u,int v,int w) {
G[++ec]={v,w,hd[u]},hd[u]=ec;
G[++ec]={u,0,hd[v]},hd[v]=ec;
}
bool bfs() {
memset(d,-1,sizeof(d)),memcpy(cur,hd,sizeof(hd));
queue <int> Q; d[S]=0,Q.push(S);
while(Q.size()) {
int u=Q.front(); Q.pop();
for(int i=hd[u];i;i=G[i].e) if(G[i].f&&d[G[i].v]<0) d[G[i].v]=d[u]+1,Q.push(G[i].v);
}
return ~d[T];
}
int dfs(int u,int f) {
if(u==T) return f;
int r=f;
for(int &i=cur[u];i;i=G[i].e) if(d[G[i].v]==d[u]+1&&G[i].f) {
int g=dfs(G[i].v,min(G[i].f,r));
if(!g) d[G[i].v]=-1;
r-=g,G[i].f-=g,G[i^1].f+=g;
if(!r) return f;
}
return f-r;
}
int n,m,dfn[105],low[105],dcnt,st[105],tp,bl[105],scnt,vis[105];
bool ins[105];
vector <int> E[105];
void tarjan(int u) {
dfn[u]=low[u]=++dcnt,ins[st[++tp]=u]=1;
for(int i=hd[u];i;i=G[i].e) if(G[i].f) {
int v=G[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) for(++scnt;ins[u];ins[st[tp--]]=0) bl[st[tp]]=scnt;
}
int k=0,h,id[105],fa[105],in[105];
LL L[105],R[105],a[105],U[105];
mt19937_64 rnd(time(0)); ull hv[105][2];
unordered_map<ull,LL>g;
ull hs(LL s) {
ull w=0;
for(int i=0;i<k;++i) w^=hv[i][s>>i&1];
return w;
}
LL dp(int i,LL s) {
if(i<0) return 1;
if(s>>i&1) return dp(i-1,s&U[i]);
ull o=hs(s|((LL)1<<i));
if(g.count(o)) return g[o];
return g[o]=dp(i-1,s&U[i])+dp(i-1,(s|a[i])&U[i]);
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m,S=2*n+1,T=S+1;
for(int i=1;i<=n;++i) link(S,i,1),link(i+n,T,1);
for(int i=1,u,v;i<=m;++i) cin>>u>>v,link(u,v+n,1);
while(bfs()) dfs(S,n);
for(int i=1;i<=T;++i) if(!dfn[i]) tarjan(i);
for(int u=1;u<=T;++u) for(int i=hd[u];i;i=G[i].e) if(G[i].f&&bl[u]!=bl[G[i].v]) E[bl[u]].push_back(bl[G[i].v]);
for(int i=1;i<=scnt;++i) {
L[i]=R[i]=(LL)1<<i;
for(int j:E[i]) R[i]|=R[j];
}
for(int i=scnt;i;--i) for(int j:E[i]) L[j]|=L[i];
for(int u=1;u<=n;++u) for(int i=hd[u];i;i=G[i].e) if(!G[i].f&&G[i].v<=2*n) if(bl[u]!=bl[G[i].v]) fa[bl[u]]=bl[G[i].v];
for(int i=1;i<=scnt;++i) id[i]=-1,in[i]=(R[bl[S]]|L[bl[T]])>>i&1;
for(int i=1;i<=scnt;++i) if(!in[i]&&id[i]<0) {
id[i]=k++;
for(int j=1;j<=i;++j) if((R[i]>>j&1)&&~id[j]) a[id[i]]|=(LL)1<<id[j];
if(fa[i]&&!in[fa[i]]) id[fa[i]]=k++,a[id[fa[i]]]=a[id[i]]|((LL)1<<id[fa[i]]);
}
for(int i=0;i<k;++i) U[i]=((LL)1<<i)-1,hv[i][0]=rnd(),hv[i][1]=rnd();
LL z=dp(k-1,0);
string Z; for(;z;z/=10) Z+=z%10+'0';
reverse(Z.begin(),Z.end()),cout<<Z<<"\n";
return 0;
}
D. [UOJ705] 黄忠庆功宴 (5)
如果 \(k\le \sqrt p\) 则前缀和，如果 \(k^{-1}\le \sqrt p\) 则可以分成 \(k^{-1}\) 个区间。
那么把 \(k\) 拆成 \(x\times y^{-1}\) 的形式，其中 \(x,y=\mathcal O( \sqrt p)\)，由于 \(ky\) 在 \(0\sim \sqrt p\) 取值时落在 \(0\sim p\) 环上最接近的两个点距离一定 \(\le\sqrt p\)，此时把这两个点相减，此时的 \(y\in [-\sqrt p,\sqrt p]\)。
那么此时对于每个 \(x\) 分别处理前缀和，然后按 \(k^{-1}\le\sqrt p\) 处理即可。
时间复杂度 \(\mathcal O((p+q)\sqrt p)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5,B=800;
int p,q,a[MAXN],e[MAXN][2];
ll iv[MAXN],f[MAXN],s[MAXN];
ll qs(int l,int r) { return r<p?s[r+1]-s[l]:s[p]-s[l]+s[r-p+1]; };
void ad(int&x,const int&y){ x=x+y>=p?x+y-p:x+y; }
vector <array<int,4>> qy[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>p>>q,iv[1]=1;
for(int i=2;i<p;++i) iv[i]=iv[p%i]*(p-p/i)%p;
for(int i=0;i<p;++i) cin>>a[i];
for(int i=1;i<p;++i) for(int k=1,r=i;!e[i][1];++k,ad(r,i)) {
if(r<=B) e[i][0]=r,e[i][1]=k;
if(r>=p-B) e[i][0]=p-r,e[i][1]=-k;
}
for(int i=1,x,k,l;i<=q;++i) cin>>x>>k>>l,x=(x-1+k-1)%p,qy[e[k][0]].push_back({x,e[k][1],l,i});
for(int x=1;x<=B;++x) if(qy[x].size()) {
for(int i=0,u=0;i<p;++i,ad(u,x)) s[i+1]=s[i]+a[u];
for(auto o:qy[x]) {
int u=o[0],y=o[1],c=o[2],k=x*iv[(y+p)%p]%p; ll &z=f[o[3]];
if(y<0) u=(u+1ll*(c-1)*k)%p,y=-y;
int h=iv[y],d=c/y-1,t=c%y; u=u*iv[x]%p;
for(int i=0;i<y;++i,ad(u,h)) z+=qs(u,u+d+(i<t));
}
}
for(int i=1;i<=q;++i) cout<<f[i]<<"\n";
return 0;
}
E. [UOJ1004] 王之沉淀 (4)
枚举 \(\texttt ?\to \texttt U\) 个数，检验的时候对于每个 \(01\) 序列判定，枚举分界线后双指针，一边扫描分界线，一边扫描当前答案并快速判定。
时间复杂度 \(\mathcal O(nk)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,MAXK=1005,MOD=998244353;
int n,m,a[MAXN],f[MAXN],b[MAXN],z[MAXN],C[MAXK][MAXK];
int qry(int x,int y) {
int c=0,p=1,w=1,s=1;
for(int k=1;k<n;++k) {
auto upd=[&]() { while(p<n&&s<w) s+=a[++p]>k; };
s-=b[k]<=p,upd();
while((n-p)-(n-k-s)>1ll*c*y) ++c,w+=x,upd();
}
return c;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string o;
cin>>n>>m>>o;
for(int i=0;i<=m;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
int U=0,D=0;
for(auto i:o) U+=i=='U',D+=i=='D';
for(int i=1;i<=n;++i) cin>>a[i],b[a[i]]=i;
for(int i=0,x;i<=m-U-D;++i) x=qry(U+i,m-U-i),z[x]=(z[x]+C[m-U-D][i])%MOD;
for(int i=0;i<n;++i) cout<<z[i]<<" \n"[i==n-1];
return 0;
}
*F. [UOJ1005] 王之钦定 (7)
取出所有极长的色数 \(\le 2\) 区间，其形态必定是 \(l,r\) 分别递增的序列，且 \(r_i<l_{i+2}\)。
那么直接 dp 记录上一个区间的范围以及结尾颜色，简单分讨当前区间去掉两侧公共部分之后的结构。
转移的时候要同时加入新的右端点和颜色，可以先钦定加入的颜色，然后去掉上一个区间的左端点从而优化转移。
转移可以斜率优化做到线性。
时间复杂度 \(\mathcal O(n^2m^2)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1505,inf=1e9;
inline void chk(int&x,const int&y) { x=y>x?y:x; }
int n,m,a[MAXN],w[MAXN],f[MAXN][MAXN][55],g[MAXN][MAXN][55],q[MAXN];
int s[MAXN],wc[55][MAXN],nx[55][MAXN],h[MAXN],mx[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i];
memset(f,-0x3f,sizeof(f)),memset(g,-0x3f,sizeof(g));
for(int i=1;i<=n;++i) {
cin>>w[i],s[i]=s[i-1]+w[i];
for(int c=1;c<=m;++c) wc[c][i]=wc[c][i-1]+(a[i]==c?w[i]:0),f[i][1][c]=wc[c][i]-s[i];
}
for(int c=1;c<=m;++c) nx[c][n+1]=n+1;
for(int i=n;i;--i) for(int c=1;c<=m;++c) {
nx[c][i]=(c==a[i+1]?i+1:nx[c][i+1]);
}
for(int i=1;i<n;++i) {
for(int j=1;j<=i;++j) for(int c=1;c<=m;++c) if(a[i+1]!=c) {
chk(g[i+1][j][c],f[i][j][c]);
int k=nx[c][i]; if(k>n) continue;
chk(g[k][j][a[i+1]],f[i][j][c]-s[k]+s[i]+wc[c][k]-wc[c][i]+wc[a[i+1]][k]-wc[a[i+1]][i]);
}
for(int j=1;j<=i;++j) for(int c=1;c<=m;++c) {
int k=nx[a[i]][i]; if(k>n) continue;
chk(g[k][j][c],g[i][j][c]-s[k]+s[i]+wc[c][k]-wc[c][i]+wc[a[i]][k]-wc[a[i]][i]);
}
for(int j=1;j<=i;++j) {
mx[j]=-inf;
for(int c=1;c<=m;++c) chk(mx[j],f[i][j][c]);
}
for(int c=1;c<=m;++c) {
int l=1,r=0;
for(int j=i;j>=1;--j) {
h[j]=max(mx[j],g[i][j][c])-i*(i-1)/2+j*(j-3)/2+1;
while(r>1&&1ll*(h[q[r-1]]-h[q[r]])*(q[r]-j)>1ll*(h[q[r]]-h[j])*(q[r-1]-q[r])) --r;
q[++r]=j;
}
for(int k=i+1;k<=n;++k) {
while(l<r&&h[q[l]]-q[l]*k<h[q[l+1]]-q[l+1]*k) ++l;
chk(f[k][i+1][c],h[q[l]]-q[l]*k-s[k]+s[i]+wc[c][k]-wc[c][i]+(i+1)*k);
}
}
}
for(int i=1;i<=n;++i) {
int z=-inf;
for(int j=1;j<=i;++j) for(int c=1;c<=m;++c) chk(z,f[i][j][c]+(i-j+1)*(i-j+2)/2);
cout<<z<<" \n"[i==n];
}
return 0;
}
G. [UOJ1012] 储存处无 (2)
\(\omega\) 个元素一块，每次用 \(\mathcal O(n)\) 把最大值属于该块的环处理，压位可以取 \(\omega=512\)。
时间复杂度 \(\mathcal O\left(\dfrac{n^2}\omega\right)\)。
更优的做法是给每个元素随机权值，然后钦定在环的最小值处翻转，判定时直接暴力遍历该环直到找到更小值，期望复杂度 \(\mathcal O(n\log n)\)
代码：
#include "perm.h"
unsigned f[16];
#define v(i) f[(i)>>5]|=1ll<<((i)&31)
#define q(i) (f[(i)>>5]>>((i)&31)&1)
void perm_work(int n) {
int l,r,x,y,z,i,o;
for(l=1;l<=n;l=r+1) {
r=l+511,r=r>n?n:r;
for(i=0;i<16;++i) f[i]=0;
for(i=l;i<=r;++i) if(!q(i-l)) {
o=0;
for(x=i;;x=perm_get(x)) {
if(x>r) o=1;
else if(x>=l) {
if(q(x-l)) break;
v(x-l);
}
}
if(o) continue;
for(x=i,y=perm_get(x);;) {
z=perm_get(y);
perm_set(y,x);
if(y==i) break;
x=y,y=z;
}
}
}
}
H. [UOJ1013] Again Counting Stars (5)
首先走一个来回相当于给 \(\le p\) 的点减一，\(\ge p\) 的点加一。
看成括号序列前缀和，限制就是 \(s_i-s_{i-1}\le a_i\)，记 \(a\) 的前缀和为 \(b\)，取 \(c_i=b_i-s_i\)，限制变为 \(c\) 递增。
只要计数 \(c_{i-1}\le c_i\le b_i\) 的序列个数，考虑容斥，钦定一段 \(c\) 递减，则只要关心段首 \(c\le b\) 限制，dp 处理是平凡的。
\(p\) 的限制就是 \(s>0\) 的点必须是一段包含 \(p\) 的区间。
那么只要算出每个前缀和后缀的答案即可。
时间复杂度 \(\mathcal O(n^2)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=8005,MOD=998244353;
int n;
ll a[MAXN],inv[MAXN],f[MAXN],L[MAXN],R[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n,inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;++i) cin>>a[i],a[i]=(a[i]+a[i-1])%MOD;
for(int i=1;i<=n;++i) {
ll x=1,y=1;
for(int j=i;j<=n;++j) {
x=x*(a[i]-j+i)%MOD*inv[j-i+1]%MOD;
y=y*(a[i-1]-j+i)%MOD*inv[j-i+1]%MOD;
f[j]=(f[j]+f[i-1]*((j-i)&1?MOD-x:x))%MOD;
f[j]=(f[j]+((j-i)&1?y+MOD-x:x+MOD-y))%MOD;
}
}
for(int i=1;i<=n;++i) L[i]=(L[i-1]+f[i-1])%MOD;
memset(f,0,sizeof(f));
for(int i=n-1;i>=1;--i) {
ll x=1,y=1;
for(int j=i;j<n;++j) {
x=x*(a[i]-j+i)%MOD*inv[j-i+1]%MOD;
y=y*(a[i-1]-j+i)%MOD*inv[j-i+1]%MOD;
R[i]=(R[i]+(f[j+1]+1)*((j-i)&1?y+MOD-x:x+MOD-y))%MOD;
f[i]=(f[i]+(f[j+1]+1)*((j-i)&1?MOD-x:x))%MOD;
}
}
for(int i=n;i>=1;--i) R[i]=(R[i]+R[i+1])%MOD;
for(int i=1;i<=n;++i) cout<<(L[n]+1+MOD-L[i-1]+MOD-R[i+1])%MOD<<" \n"[i==n];
return 0;
}
*I. [UOJ1014] Ad-hoc Master II (7.5)
朴素的想法肯定是直接询问 \(\sum f(u,1)\) 然后求出一些深度的点调整答案。
这样的做法次数太多，一个优化思路就是去掉较深的几层，此时可以大幅减少 \(n\) 范围。
可以询问 \(f(u,2h-2)\) 从而得到深度为 \([h-2,h]\) 的点，以及 \(\sum f_(u,1)\) 解决这部分的权值和。
然后进一步对深度 \(\le h-3\) 的点询问 \(f(u,h+2)\) 求出前两层的点，进一步找到根。
此时我们得到的 \(\sum f\) 总是每层的权值和的线性组合，进一步只要关心 \(h-3\sim h\) 这些层即可，其他层容易解决。
那么上面的两组 \(\sum f\) 能得到向量 \((1,1,0,0),(0,0,0,1),(0,4,2,3)\)，询问深度为 \(1\) 的点 \(h-2\) 得到 \((1,0,1,0)\) 即可合法。
简单优化可以少掉两次，从而满足题目限制。
时间复杂度 \(\mathcal O(n)\)。
更优的做法就是总结上述过程，首先通过一些方法给每个点确定层数，然后用形如 \(w(l,r,d)=\sum_{l\le d_u\le r}f(u,d)\) 的询问得到一些每个深度权值和的线性组合，搜索出一组能组合出 \([1,1,\dots,1]\) 的方案即可。
代码：
#include<bits/stdc++.h>
#include "tree.h"
#define ll long long
using namespace std;
const int MAXN=1<<18|5;
ll a[MAXN],b[MAXN];
ll solve(int,int h) {
int n=(1<<h)-1; --h,fill(a,a+n+1,0);
vector <int> H,rt;
if(h==2) {
for(int i=1;i<n;++i) a[i]=ask(i,4),a[n]^=a[i];
ll s0=0,s1=0;
for(int i=1;i<=n;++i) {
s0+=a[i];
if(!a[i]) rt.push_back(i);
}
int p=0; s0/=2;
while(p<2&&ask(rt[p],3)) ++p;
for(int x:rt) if(x^rt[p]) s1+=ask(x,1);
return ask(rt[p],1)+s0+(s1-s0)/2;
} else if(h<4) {
for(int i=n;i&&rt.size()<3;--i) {
if(rt.size()+i-1<3||!ask(i,h+2)) rt.push_back(i);
}
ll s1=0;
for(int i:rt) {
ll z=ask(i,h+1);
if(z) s1+=ask(i,1),a[h]+=z;
else for(int d=h-1;d;--d) a[d]=ask(i,d);
}
return accumulate(a+1,a+h+1,0ll)+(s1-a[2])/2;
}
for(int i=1;i<n;++i) a[i]=ask(i,2*h-2),a[n]^=a[i];
ll s0=0,s1=0,s2=0,s3=0,s4=0; //s0=1100, s1=0001, s2=rt, s3=0423, s4=1010
for(int i=1;i<=n;++i) {
s3+=a[i];
if(!a[i]) H.push_back(i);
}
for(int i:H) b[i]=ask(i,1),s0+=b[i];
for(int i=H.size()-1;~i&&rt.size()<3;--i) {
if(rt.size()+i<3||!ask(H[i],h+2)) rt.push_back(H[i]);
}
for(int i:rt) {
ll z=ask(i,h+1);
if(z) s1+=z,s2+=b[i],s4+=ask(i,h-2);
else s2-=ask(i,2);
}
s3>>=h-3;
return (s0+s2/2+(s1*3+s3)/2+s4*2)/3;
}
*J. [UOJ1015] 我的 XOR 卷积人生 (8.5)
考虑朴素 XOR 卷积时如何设计 FWT 变换，考虑 \(n=1\) 的情况，\((a_0,a_1)\times (b_0,b_1)=(a_0b_0+a_1b_1,a_0b_1+a_1b_0)\)。
那么我们想构造 \(x_0,x_1\) 的线性组合，使得 XOR 卷积后得到的结果就是对应线性组合的直接乘积，即 \((a_0+ka_1)(b_0+kb_1)=a_0b_0+a_1b_1+ka_0b_1+ka_1b_0\)，解得 \(k^2=1\)。
即 \(k=\pm 1\) 时，体现在 FWT 上就是 \((a_0,a_1)\to (a_0+a_1,a_0-a_1)\)，同理可以推出 OR 和 AND 卷积的表示。
考虑子集卷积的形式：\((a_0+ka_1)(b_0+kb_1)=a_0b_0+ka_0b_1+ka_1b_0\)，解得 \(k^2=0\)，此时具有重根。
我们的解决方法是带入 \(k=0\) 和 \(k=\epsilon\)，维护一个关于 \(\epsilon\) 的多项式，最后令 \(\epsilon\gets 0\) 即可。
对于 XOR 卷积，我们的问题是 \(2\mid M\) 时不存在 \(\bmod 2\) 逆元，类似上面的过程取 \(k=1,\epsilon-1\) 即可。
但这个做法并不直观，考虑将 \(k\) 平移为 \(k+1\)，即 \((a_0,a_1)\gets (a_0+a_1,a_1)\)，此时限制变为 \(k^2-2k=0\)。
在子集卷积时带入 \(\epsilon=2\) 即可，该限制对应的组合意义是 \((a_0+ka_1)(b_0+kb_1)=a_0b_0+ka_0b_1+ka_1b_0+2ka_1b_1\)，即 \(c_{S\cup T}\gets a_Sb_T2^{|S\cap T|}\)，组合意义上与计算过程吻合。
时间复杂度 \(\mathcal O(n^22^n)\)。
代码：
#include<bits/stdc++.h>
#include "xor.h"
using namespace std;
int h[1<<19];
mat f[40][1<<19],g[20][1<<19];
vector<mat> xor_convolution(vector<mat>a,vector<mat>b,int) {
int n=a.size(),m=__lg(n);
for(int k=1;k<n;k<<=1) for(int i=0;i<n;++i) if(i&k) a[i-k]-=a[i],b[i-k]-=b[i];
for(int i=0;i<n;++i) h[i]=h[i>>1]+(i&1),f[h[i]][i]=a[i],g[h[i]][i]=b[i];
for(int c=0;c<=m;++c) for(int k=1;k<n;k<<=1) for(int i=0;i<n;++i) if(i&k) f[c][i]+=f[c][i-k],g[c][i]+=g[c][i-k];
for(int i=0;i<n;++i) {
vector<mat>X(m+1),Y(m+1);
for(int c=0;c<=m;++c) X[c]=f[c][i],Y[c]=g[c][i];
X=convolution(X,Y);
for(int c=0;c<=2*m;++c) f[c][i]=X[c];
}
for(int c=0;c<=2*m;++c) for(int k=1;k<n;k<<=1) for(int i=0;i<n;++i) if(i&k) f[c][i]-=f[c][i-k];
for(int i=0;i<n;++i) {
a[i]=0;
for(int c=2*m;c>=h[i];--c) a[i]=a[i]+a[i]+f[c][i];
}
for(int k=1;k<n;k<<=1) for(int i=0;i<n;++i) if(i&k) a[i-k]+=a[i];
return a;
}
K. [UOJ918] 偷吃蛋糕（3）
容易想到要直接爆搜，在得到所有蛋糕后返回，并且在枚举时只考虑本质不同的蛋糕。
时间复杂度 \(\mathcal O(nS)\)，其中 \(S\approx 5\times 10^7\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005,MOD=998244353;
int n,a[MAXN],s[MAXN],iv[MAXN];
bool vis[MAXN];
int dfs(int x,int l,int w) {
if(w>=n) {
for(int r;l<=n;++x) if(!vis[x]) {
r=min(n,l+a[x]-1),w=(w+1ll*(r-l)*iv[r-l+1]%MOD*(s[r]-s[l-1]))%MOD,l=r+1;
}
return (w+MOD-n+1)%MOD;
}
while(vis[x]) ++x;
int z=0,r=min(l+a[x]-1,n);
for(int i=l,j;i<=r;i=j) {
for(j=i;j<=r&&a[i]==a[j];++j);
vis[i]=1,z=(z+1ll*(j-i)*iv[r-l+1]%MOD*dfs(x+1,r+1,w+s[r]-s[l-1]-a[i]))%MOD,vis[i]=0;
}
return z;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n,iv[1]=1;
for(int i=2;i<=n;++i) iv[i]=1ll*(MOD-MOD/i)*iv[MOD%i]%MOD;
for(int i=1;i<=n;++i) cin>>a[i],s[i]=s[i-1]+a[i];
cout<<dfs(1,2,a[1])<<"\n";
return 0;
}
*L. [UOJ919] 环环相扣 (8.5)
设 \(a_i>a_j>a_k\)，则本质不同权值只有 \(a_i\bmod a_j+a_j\bmod a_k+a_k\) 或 \(a_i\bmod a_k+a_j+a_k\)。
可以证明选出的 \(i,j\) 必定是区间最大次大值。
假设询问 \([1,n]\) 且 \(a\) 递增，则显然下界是 \(a_{n-2}+a_{n-1}\)，如果不同时选择 \(a_n,a_{n-1}\) 显然无法取到该值。
这是因为对于 \(a_i>a_j\)，\(a_i\bmod a_j+a_j\le a_i\)，则任何权值不超过 \(a_i+a_j\)。
那么只要计算 \(f(l,r,i)\) 表示 \(\max _{l\le j\le r} a_j+a_i\bmod a_j\)，其中 \(j\) 不是 \(a[l,r]\setminus a_i\) 的最大值，其中 \(a_i\) 是 \(a[l,r]\) 中前二大值。
显然对 \([l,i],[i,r]\) 独立，只考虑第一个问题。
暴力扫描支配对，如果存在 \(2a_j>a_i\) 则取到最大值 \(a_i\)，如果存在两个这样的 \(j\)，那么 \(l\) 更小时 \(f\) 必取到 \(a_i\)。
如果扫描到的 \(a_j>a_i\)，则扫到两个元素后这样的 \(f(l,i,i)\) 不满足 \(a_i\) 是 \(a[l,r]\) 中前二大值。
此时支配对数 \(\mathcal O(n\log V)\)。
进一步优化，如果当前 \([j,i]\) 中有两个 \(\ge 2a_j\) 的元素，很显然选择这样的元素得到的值 \(\ge 2a_j> a_j+a_i\bmod a_j\)。
所以直接用栈维护所有 \(j\)，每次从上到下暴力遍历栈，如果遇到两个 \(2a_j>a_i\) 就返回，否则这个 \(a_j\) 被保留次数 \(+1\)，如果保留次数 \(\ge 2\) 则删除这个 \(j\)，此时支配对数线性。
时间复杂度 \(\mathcal O(n+q\log n)\)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e6+5,N=1<<21;
int n,m,ty,b[MAXN],c[MAXN],h;
ll a[MAXN];
struct info {
int x,y;
friend info operator +(const info&u,const info&v) {
if(a[u.x]<a[v.x]) return {v.x,a[u.x]>a[v.y]?u.x:v.y};
else return {u.x,a[v.x]>a[u.y]?v.x:u.y};
}
} tr[N<<1];
info mx(int l,int r) {
info s={0,0};
for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {
if(~l&1) s=s+tr[l^1];
if(r&1) s=s+tr[r^1];
}
return s;
}
void ins(int x,auto&Z) {
int o=h,p=0; ll z=0;
for(int w=2;h;--h) {
int q=b[h];
if(2*a[q]<=a[x]) ++c[q];
else if(!--w) { Z.push_back({q,a[x]}); break; }
if(a[q]>a[p]) swap(p,q);
if(q) Z.push_back({b[h],z=max(z,a[x]%a[q]+a[q])});
}
for(int i=h+1;i<=o;++i) if(c[b[i]]<=2) b[++h]=b[i];
b[++h]=x;
}
vector <pair<int,ll>> f[MAXN],g[MAXN];
ll qry(int l,int r,int x) {
ll t=min(a[mx(l,x-1).x],a[mx(x+1,r).x]),z=t?a[x]%t+t:0;
if(l<x-1) z=max(z,lower_bound(f[x].begin(),f[x].end(),make_pair(l,0ll))->second);
if(x+1<r) z=max(z,(--lower_bound(g[x].begin(),g[x].end(),make_pair(r+1,0ll)))->second);
return z;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>ty;
for(int i=1;i<=n;++i) cin>>a[i],tr[i+N]={i,0};
for(int i=N-1;i;--i) tr[i]=tr[i<<1]+tr[i<<1|1];
for(int i=1;i<=n;++i) ins(i,f[i]),reverse(f[i].begin(),f[i].end());
memset(c,0,sizeof(c)),h=0;
for(int i=n;i>=1;--i) ins(i,g[i]);
for(ll z=0,l,r;m--;) {
cin>>l>>r,l=(l-1+z)%n+1,r=(r-1+z)%n+1;
auto o=mx(l,r);
z=max(qry(l,r,o.x)+a[o.y],qry(l,r,o.y)+a[o.x]%a[o.y]);
cout<<z<<"\n",z*=ty;
}
return 0;
}
浙公网安备 33010602011771号