六道题目的出题人都是我，希望大家玩的开心！
https://ac.nowcoder.com/acm/contest/51208
A. 惊鸿
显然位或之后只会变大，因此答案为 \(4\times (a_1\text{ or }a_2\text{ or }a_3\text{ or }a_4)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
signed main(void){
int tt=read();while(tt--){
int a=read(),b=read(),c=read(),d=read();
cout<<((a|b|c|d)<<2)<<endl;
}
return 0;
}
B. 风间
有解必须要 \(\forall i,a_i\equiv b_i\pmod2\)，且 \(\sum_{i=1}^na_i=\sum_{i=1}^nb_i\)。
那么首先判掉无解，如果有解，记 \(f_i=\sum_{j\le i}a_j,g_i=\sum_{j\le i}b_j\)，答案就是 \(\sum_{i=1}^n\frac{|f_i-g_i|}{2}\)
略证：考虑每个 \(1\le i<n\)，算出 \(i,i+1\) 之间转移了多少次。当 \(f_i>g_i\) 时，左侧有 \(f_i-g_i\) 这么多值要转到右边去，每次最多转移 \(2\)，因此贡献至少为 \(\frac{f_i-g_i}{2}\)；\(f_i<g_i\) 时同理。显然可以构造出方案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int N=2e5+5;
int a[N],b[N],n;
void solve(){
n=read();int ans=0,A=0,B=0;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=n;i++){
if(a[i]%2!=b[i]%2){puts("-1");return ;}
A+=a[i],B+=b[i],ans+=(max(A,B)-min(A,B))>>1;
}
if(A!=B){puts("-1");return ;}
cout<<ans<<endl;
}
signed main(void){
int tt=read();
while(tt--)solve();
return 0;
}
C. 梦迹
考虑开一个桶，记 \(c_i\) 为满足 \(a_x=i\) 的 \(x\) 的个数，再设其前缀和 \(f_i=\sum_{j=1}^ic_j\)。
如果不考虑 \(i\le j\) 的限制，那么答案就是
\[\sum_{i=0}^Wc_if_{W-i}\tag{1} \]一次修改相当于将某个 \(c_x\leftarrow c_x+1,c_y\leftarrow c_y-1\)。考虑 \(c_x\leftarrow c_x+1\) 对答案的影响。
分两种情况讨论：
- \(2x>W\)：这种情况比较简单，\((1)\) 式的第 \(0,1,\cdots,W-x\) 项与第 \(x\) 项发生了改变。对于 \(i\le W-x\)，\(c_if_{W-i}\) 变为了 \(c_i(f_{W-i}+1)\)，增加了 \(c_i\)；对于第 \(x\) 项，\(c_xf_{W-x}\) 变为 \((c_x+1)f_{W-x}\)，增加了 \(f_{W-x}\)。因此只需将答案加上 \(f_{W-x}+\sum_{i\le W-x}c_i=2f_{W-x}\)，再处理对应的 \(c,f\) 的改动即可。
- \(2x\le W\)：此时 \((1)\) 式的第 \(0,1,\cdots,W-x\) 项发生改变，但第 \(x\) 项的改变不同。对于 \(i\le W-x\) 且 \(i\neq x\)，这一项的增加仍为 \(c_i\)；但对于第 \(x\) 项，由 \(c_xf_{W-x}\) 变成了 \((c_x+1)(f_{W-x}+1)\)，增加了 \(c_x+f_{W-x}+1\)，因此总的增幅为 \(2f_{W-x}+1\)。
使用树状数组维护单点加与前缀和，复杂度 \(O((n+q)\log V)\)，其中 \(V=3\times 10^5\) 为值域。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int N=3e5+5;
int n,q,W,a[N],cnt,ans;
struct BIT{
int c[N];
int lowbit(int x){return x&(-x);}
void add(int x,int k){x++;for(int i=x;i<=W+1;i+=lowbit(i))c[i]+=k;}
int sum(int x,int res=0){x++;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
}T;
void Modify(int x,int k){
cnt+=k*(x+x<=W);
if(x+x>W)ans+=k*2*T.sum(W-x),T.add(x,k);
else ans+=k*2*T.sum(W-x)+1,T.add(x,k);
}
signed main(void){
n=read(),q=read(),W=read();
for(int i=1;i<=n;i++)a[i]=read(),Modify(a[i],1);
for(int i=1;i<=q;i++){
int p=read(),x=read();Modify(a[p],-1),Modify(x,1),a[p]=x;
cout<<(ans+cnt)/2<<endl;
}
return 0;
}
D. Small Cloud Sugar Candy
BV1Uy4y137SA
对每条限制连边，那么得到一张无向图。考虑每个连通块，
- 若存在奇环，那么奇环上的点权都可以直接确定，进而确定整个连通块，看看是否有矛盾即可。具体来说，如果我们找到了一个奇环，设其上的边权分别为 \(w_1,w_2,\cdots,w_k\)，其中 \(w_i\)（\(1\le i<k\)） 连接 \(a_i,a_{i+1}\)，\(w_k\) 连接 \(a_k,a_1\)，那么 \(a_x=\frac{w_1-w_2+\cdots,-w_{k-1}+w_k}{2}\)。
- 否则，我们随便钦定一个点，让它的权值为 \(0\)（或者任意数），那么整个连通块的值都可以确定。确定后看是否有矛盾即可。
时间复杂度 \(O(n+m)\)。显然构造出的序列每一项都在 \([-10^{18},10^{18}]\) 中。
Bonus：
- 实际上我们也可以构造出满足 \(a_i\) 仍然在 \([0,10^9]\) 内的解
- 并且能构造字典序最小的解，还能输出方案数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int N=5e5+5;
struct Edge{
int cost,to;
Edge(int T,int C):to(T),cost(C){}
Edge(){}
};
vector<Edge>G[N];
int dep[N],fa[N],val[N],a[N],fir;
bool chk=0,vis[N],calc[N];
bool Ans=1;
void dfs1(int u){
vis[u]=1;
for(auto t:G[u]){
int v=t.to,w=t.cost;
if(v==fa[u])continue;
else if(!vis[v]){dep[v]=dep[u]+1,fa[v]=u,val[v]=w,dfs1(v);continue;}
if((!chk)&&(dep[u]-dep[v]+1)%2==1){
int p=u,now=1,sum=w;
while(p!=v)sum+=val[p]*now,now=-now,p=fa[p];
if(sum%2!=0)Ans=0;
a[u]=sum/2,fir=u,chk=1,calc[u]=1;
}
}
}
void dfs2(int u){
calc[u]=1;
for(auto t:G[u]){
int v=t.to,w=t.cost;
if(!calc[v])a[v]=w-a[u],dfs2(v);
else if(calc[v]&&a[u]+a[v]!=w)Ans=0;
}
}
int n,m,fr[N],to[N],we[N];
void solve(){
n=read(),m=read();Ans=1;
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();fr[i]=u,to[i]=v,we[i]=w;
G[u].push_back(Edge(v,w)),G[v].push_back(Edge(u,w));
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
chk=0,fir=i,dfs1(i),dfs2(fir);
}
if(!Ans)puts("-1");
else{for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts("");}
for(int i=1;i<=n;i++)dep[i]=fa[i]=val[i]=a[i]=calc[i]=vis[i]=0;fir=chk=0;
for(int i=1;i<=n;i++)G[i].clear();
}
signed main(void){
int tt=read();while(tt--)solve();
return 0;
}
E. 琉焰
对于每次询问，设 \(k\) 为此时连通块数量，\(m\) 为此时的边数，那么答案就是 \(2^{m-n+k}-1\)。
为什么呢，首先可以对每个连通块单独考虑。随便拎出来一个生成树，那么合法的方案与非树边的非空子集一一对应。一个大致的证明如下：
-
对于任意一个非树边的非空子集，我们考虑这样构造方案：对于这个子集中的每条边 \((u,v)\)，将森林中 \(u\to v\) 的路径上的所有边以及 \((u,v)\) 这条边覆盖一次，那么最终我们选取的边集就是所有覆盖次数为奇数的边组成的集合。不难验证这个生成子图确实符合条件。
-
考虑一个符合条件的生成子图，那么图中的每个连通块都存在一条欧拉回路。欧拉回路一定可以被拆分成若干个环的并，而在上面的构造方式中，每个环的刻画方式是唯一的。因此两边就一一对应了。
一个连通块的非树边数量是 边数 - 点数 +1，当有 \(k\) 个连通块时，方案数就是 \(2^{m-n+k}-1\)，减一是减去空集。
考虑线段树分治，把 \((u,v)\) 的存在区间拆成 \(O(\log n)\) 个小区间插入线段树，然后 DFS 整棵树并处理对应的修改即可。
使用可撤销并查集维护连通块个数，时间复杂度不会超过 \(O((n+m)\log ^2(n+m))\)。
//我是宵宫小姐的狗
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int mod=998244353;
int ksm(int x,int y,int p=mod){
int ans=1;
for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
int randint(int l,int r){return rand()*rand()%(r-l+1)+l;}
#define fi first
#define se second
#define mk make_pair
const int N=2e5+5;
int n,m;
map<pair<int,int>,int>Map;
int fa[N],sz[N],top=0,cnt=0,P[N];
pair<int,int>stk[N];
int find(int x){return x==fa[x]?x:find(fa[x]);}
void adde(int x,int y){
x=find(x),y=find(y);
if(x==y)return ;
if(sz[x]>sz[y])swap(x,y);
sz[y]+=sz[x],fa[x]=y,stk[++top]=mk(x,y),cnt--;
}
void undo(int id){
int x=stk[id].fi,y=stk[id].se;
sz[y]-=sz[x],fa[x]=x,cnt++;
}
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
vector<pair<int,int> >vec[N<<2];
void add(int l,int r,pair<int,int>k,int ql,int qr,int p){
if(l<=ql&&qr<=r){vec[p].emplace_back(k);return ;}
int mid=(ql+qr)>>1;
if(l<=mid)add(l,r,k,ql,mid,ls(p));
if(r>mid)add(l,r,k,mid+1,qr,rs(p));
}
int Ans[N],cur[N];
void dfs(int ql,int qr,int p){
int now=top;for(auto t:vec[p])adde(t.fi,t.se);
if(ql==qr){Ans[ql]=P[cur[ql]-n+cnt]-1;while(top>now)undo(top--);return ;}
int mid=(ql+qr)>>1;dfs(ql,mid,ls(p)),dfs(mid+1,qr,rs(p));
while(top>now)undo(top--);
}
int st[N],ed[N],fr[N],to[N];
signed main(void){
n=read(),m=read();int tot=0;
for(int i=1;i<=m;i++){
int u=read(),v=read();auto it=Map.find(mk(u,v));
if(it==Map.end())Map[mk(u,v)]=i,cur[i]=cur[i-1]+1;
else st[++tot]=it->se,ed[tot]=i-1,fr[tot]=u,to[tot]=v,Map.erase(it),cur[i]=cur[i-1]-1;
}
for(auto it:Map)st[++tot]=it.se,ed[tot]=m,fr[tot]=it.fi.fi,to[tot]=it.fi.se;
P[0]=1;for(int i=1;i<=m;i++)P[i]=(P[i-1]<<1)%mod;
for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;cnt=n;
for(int i=1;i<=tot;i++)add(st[i],ed[i],mk(fr[i],to[i]),1,m,1);
dfs(1,m,1);for(int i=1;i<=m;i++)cout<<Ans[i]<<'\n';
return 0;
}
F. wavedash.ppt
首先我们把平方拆开，有
\[f(S)=\sum_{V(P)\subseteq S,V(Q)\subseteq S}W(P)W(Q) \]考虑交换求和顺序，枚举 \(P,Q\)，有
\[\begin{aligned}\sum_{S\subseteq \{1,2,\cdots,n\}}f(S)&=\sum_{P,Q}2^{n-|V(P)\cup V(Q)|}W(P)W(Q)\\&=2^n\sum_{P,Q}2^{-|V(P)\cup V(Q)|}W(P)W(Q)\end{aligned} \]注意到 \(|A\cup B|=|A|+|B|-|A\cap B|\)，因此上式即
\[2^n\sum_{P,Q}2^{|V(P)\cap V(Q)|}\times 2^{-|V(P)|}W(P)\times 2^{-|V(Q)|}W(Q) \]我们定义 \(W'(P)=2^{-|V(P)|}W(P)\)，则只需要求
\[\begin{aligned}\sum_{P,Q}2^{|V(P)\cap V(Q)|}W'(P)W'(Q)&=\sum_{P,Q}\left(\sum_{T}[T\subseteq \big(V(P)\cap V(Q)\big)]\right)W'(P)W'(Q)\\&=\sum_{T}\sum_{T\subseteq V(P),T\subseteq V(Q)}W'(P)W'(Q)\end{aligned} \]考虑设 \(g(u)\) 表示 \(T\) 中拓扑序最小的点为 \(u\)（这里认为存在连边 \(u\to v\) 则 \(u\) 的拓扑序小于 \(v\)），且只计入从 \(u\) 开始的路径 \(P,Q\)，但不计入 \(u\) 的贡献，此时的所有 \((T,P,Q)\) 的贡献之和；同时预处理 \(s(u,v)\) 表示所有从 \(u\) 开始到 \(v\) 结束的路径 \(P\)，但不计入 \(u\) 的贡献的 \(W'(P)\) 之和，那么有转移
\[g(u)\leftarrow g(v)\times s(u,v)^2 \]同时定义
\[s(0,v)=\sum_{n\ge u\ge 1}\frac{w_u}{2}\times s(u,v),s(v,n+1)=\sum_{1\le u\le n}s(v,u)\quad(1\le v\le n)\\ s(0,n+1)=\sum_{1\le u,v\le n}s(u,v)\times \frac{w_u}{2} \]并类似地定义 \(g(0)\)，则初值为 \(g(n+1)=1\)，答案即为 \(g(0)\)。
拓扑排序后 DP 即可。时间复杂度为 \(O(n^2+nm)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
const int mod=998244353;
int ksm(int x,int y,int p=mod){
int ans=1;
for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
int randint(int l,int r){return rand()*rand()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
const int N=4005;
const int iv=inv(2);
int f[N][N],g[N],n,m,w[N],ind[N];
vector<int>G[N],tp;
queue<int>q;
bool topo(){
for(int i=1;i<=n;i++)if(!ind[i])q.push(i);
while(q.size()){
int x=q.front();q.pop();tp.emplace_back(x);
for(int v:G[x])if(--ind[v]==0)q.push(v);
}
return (tp.size()==n+1);
}
signed main(void){
n=read(),m=read();
for(int i=1;i<=n;i++)w[i]=read()*iv%mod;
for(int i=1;i<=m;i++){int u=read(),v=read();G[u].emplace_back(v),ind[v]++;}
tp.emplace_back(0);assert(topo());tp.emplace_back(n+1);
for(int i=1;i<=n;i++){
int u=tp[i];f[u][u]=1;
for(int j=i;j<=n;j++){
int v=tp[j];for(int x:G[v])add(f[u][x],f[u][v]*w[x]%mod);
}
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)add(f[0][i],f[j][i]*w[j]%mod),add(f[i][n+1],f[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)add(f[0][n+1],f[i][j]*w[i]%mod);
g[n+1]=1;for(int i=n;i>=0;i--){
for(int j=i+1;j<=n+1;j++)add(g[tp[i]],g[tp[j]]*f[tp[i]][tp[j]]%mod*f[tp[i]][tp[j]]%mod);
}
cout<<g[0]*ksm(2,n)%mod<<'\n';
return 0;
}