本着 10 月杂题题解只记重量级的原则，再加上这个系列好久没更新了，搞一发。
发挥还可以的一场，至少比 csp-s 发挥的好。
- T1 智慧概率题，考场差点出来，30 pts。
- T2 简单计数题，之前几场都卡 T2，终于出来一次，100 pts。
- T3 简单数据结构题，打的 30 pts 暴力，但是有 50 pts。
- T4 智慧网络流建模题，随便打了个 30 pts 暴力。
T1 赢钱
设 \(f(i)\) 表示当前有 \(i\) 元钱，得到 \(b\) 元钱的概率。
那么有：
\(\begin{cases} f(i)=Pf(2i) \ \ \ \ 2i\leq b \\ f(i)=(1-P)f(2i-b)+P \ \ \ \ 2i > b \end{cases}\)
然后你会发现转移可能形成了一个环。
比如转移顺序可能是这样的： \(f(a) \leftarrow f(b) \leftarrow f(c) \leftarrow f(a)\)。
设 \(f(a)=x\)，带进去算，那么最后会得到 \(f(a)=x=kx+b\)，然后就可以解得 \(x\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=998244353;
int a,b,P,Q,f,cnt,p[N],vis[N];//p[i]：第 i 次转移是哪种情况
int qpow(int a,int b) {int r=1;for(;b;b>>=1,a=a*a%mod) if(b&1) r=r*a%mod;return r;}
int inv(int a) {return qpow(a,mod-2);}
signed main()
{
cin>>a>>b>>P;
P=P*inv(1e6)%mod,Q=(1-P+mod)%mod;
while(!vis[a]) vis[a]=++cnt,p[cnt]=(a*2>=b),a=a*2%b;
int k=1,b=0;
for(int i=cnt;i>=vis[a];i--)
{
if(p[i]) k=k*Q%mod,b=(b*Q+P)%mod;
else k=k*P%mod,b=b*P%mod;
}
f=b*inv(1-k+mod)%mod;
for(int i=vis[a]-1;i;i--)
{
if(p[i]) f=(f*Q+P)%mod;
else f=f*P%mod;
}
cout<<f;
}
T2 排列
考虑把每个位置看为一个点，一个限制看为一条无向边。
然后得到一张图。
显然每个点度数不能大于 \(2\)。
图中连通块之间的限制基本是独立的。
假设当前连通块大小为 \(sz\)。
若当前连通块是个环，那么这些位置就有两种填法，会限制 \(sz\) 个位置。
若是一个链，还分两种情况。
若链的大小 \(>2\)，那么两种填法至少有一个位置不相同，所以是两种，会限制 \(sz-1\) 个位置。
若链的大小 \(<2\)，不能直接是两种填法，可能重复，会限制 \(1\) 个位置。
设总共有 \(k\) 条链的大小 \(<2\)，有 \(p\) 个位置没有限制。
枚举有多少大小 \(<2\) 的链，限制了两个位置，容斥即可，那么对于这 \(k\) 条链，方案为：
\(\sum\limits_{0\leq i \leq k} (-1)^i \binom{k}{i}2^{k-i}(p-i)!\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,p=998244353;
int n,m,k,sum,ans=1,sz,_sz,lian;
int vis[N],pw[N]={1},fac[N]={1},inv[N];
vector<int> G[N];
map<pair<int,int>,bool> mp;//判重边
int qpow(int a,int b) {int r=1;for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r;}
int C(int n,int m) {if(n<m) return 0;return fac[n]*inv[m]%p*inv[n-m]%p;}
void dfs(int x)
{
vis[x]=1;_sz++;
if(G[x].size()<2) lian=1;
for(int y:G[x]) if(!vis[y]) dfs(y);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;sz=n;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%p;
inv[n]=qpow(fac[n],p-2);
for(int i=n-1;~i;i--) inv[i]=inv[i+1]*(i+1)%p;
for(int i=1;i<=m;i++)
{
int x,y;cin>>x>>y;
if(x>y) swap(x,y);
if(mp.count({x,y})) continue;
G[x].push_back(y),G[y].push_back(x);
mp[{x,y}]=1;
}
for(int i=1;i<=n;i++) if(G[i].size()>2) {cout<<0;return 0;}
for(int i=1;i<=n;i++) if(G[i].size()&&i==*G[i].begin()) sz--;//自环
for(int i=1;i<=n;i++)
if(!vis[i])
{
_sz=lian=0;
dfs(i);
if(_sz==1) continue;
if(_sz==2) sz--,k++;
else ans=ans*2%p,sz-=_sz-lian;
}
for(int i=0;i<=k&&i<=sz;i++) sum=(sum+((i&1)?-1:1)*pw[k-i]*C(k,i)%p*fac[sz-i]%p+p)%p;
cout<<ans*sum%p;
}
T3 箱子
显然颜色相同的段之间独立。
一个很显然的结论，每次选尽可能大的区间进行操作。
那么对于一个点 \(i\)，其作为左端点的次数为 \(\max(a_i-a_{i-1},0)\)，作为右端点的次数为 \(\max(a_i-a_{i+1},0)\)。
如果 \(c_i \neq c_{j}\) 或者 \(i\) 作为某次询问的边界，那么在上面式子里对应 \(a_{j}=0\)。
考虑对于两种贡献用线段树分别维护，第一种单点修就用那个公式直接搞就完了，然后维护区间和。
然后另一棵线段树维护某些位置作为颜色段边界的贡献（草，这玩意好像可以用 BIT）。
对于一段颜色覆盖，可以用 ODT，个人感觉 ODT 巨难写，巨难调，巨容易错，一开始我就写错了近 10 个地方，调了 2.5 h。
而好多大神都没用 ODT。
复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=2e9;
int n,q,ans,c[N],w[N],a[N],b[N],isR[N];//isR：位置 i 是不是右端点
struct node{
int l,r,col;
bool operator<(const node&x)const{
if(l==x.l) return r>x.r;
return l<x.l;
}
};
set<node> s;
inline int rd()
{
int x=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
#define lc (k<<1)
#define rc (k<<1|1)
#define mid (l+r>>1)
int sum[N<<2],sum2[N<<2];
void build(int k=1,int l=1,int r=n)
{
if(l==r) {sum[k]=(max(a[l]-a[l-1],0ll)+max(a[l]-a[l+1],0ll))*w[l];return;}
build(lc,l,mid),build(rc,mid+1,r);
sum[k]=sum[lc]+sum[rc];
}
void upd(int x,int k=1,int l=1,int r=n)
{
if(x<0||x>n) return;
if(l==r) {sum[k]=(max(a[l]-a[l-1],0ll)+max(a[l]-a[l+1],0ll))*w[l];return;}
x<=mid?upd(x,lc,l,mid):upd(x,rc,mid+1,r);
sum[k]=sum[lc]+sum[rc];
}
void upd2(int x,int v,int k=1,int l=1,int r=n)
{
if(x<0||x>n) return;
if(l==r) {sum2[k]+=v;return;}
x<=mid?upd2(x,v,lc,l,mid):upd2(x,v,rc,mid+1,r);
sum2[k]=sum2[lc]+sum2[rc];
}
int qsum(int x,int y,int k=1,int l=1,int r=n)
{
if(l>=x&&r<=y) return sum[k]+sum2[k];
int res=0;
if(x<=mid) res+=qsum(x,y,lc,l,mid);
if(mid<y) res+=qsum(x,y,rc,mid+1,r);
return res;
}
void Upd2(int i,int v) {upd2(i,v*min(a[i],a[i+1])*w[i]),upd2(i+1,v*min(a[i],a[i+1])*w[i+1]);}
signed main()
{
n=rd(),q=rd();
for(int i=1;i<=n;i++) a[i]=rd(),c[i]=rd(),w[i]=rd();
build();
s.insert({-inf,-inf,0}),s.insert({inf,inf,0});
for(int i=1;i<=n;i++)
{
int j=i;
while(j<n&&c[j+1]==c[i]) j++;
if(j!=n) Upd2(j,1);
isR[j]=1;
s.insert({i,j,c[i]});
i=j;
}
while(q--)
{
int op=rd();
if(op==1)
{
int x=rd();
if(isR[x]) Upd2(x,-1);
if(isR[x-1]) Upd2(x-1,-1);
a[x]=rd(),w[x]=rd();
//注意这里会影响三个位置的值
upd(x),upd(x-1),upd(x+1);
if(isR[x]) Upd2(x,1);
if(isR[x-1]) Upd2(x-1,1);
}
else if(op==2)
{
int l=rd(),r=rd(),v=rd();
auto it=s.lower_bound({l,r,v});
for(;it->l<=r;++it,s.erase(prev(it)))//合并左端点在 [l,r] 内的区间
{
auto [_l,_r,col]=*it;
if(_r<=r) isR[_r]=0,Upd2(_r,-1);
else
{
if(v==col) isR[_r]=0,Upd2(_r,-1),r=_r;//颜色相同扩大右端点
else s.insert({r+1,_r,col});
}
}
it=s.lower_bound({l,r,v});--it;
auto [_l,_r,col]=*it;
//合并右端点在 [l,r] 的区间
//注意一定要先考虑某个超大区间包含了 [l,r] 的情况
if(col==v) s.erase(it),isR[_r]=0,Upd2(_r,-1),l=_l,r=max(r,_r);
else if(it->r>=l)
{
s.erase(it);
if(_l<=l-1) s.insert({_l,l-1,col}),isR[l-1]=1,Upd2(l-1,1);
if(_r<=r) isR[_r]=0,Upd2(_r,-1);
else s.insert({r+1,_r,col});
}
it=s.lower_bound({l,r,v});
//有可能有 [r+1,_r] 这种和当前颜色相同的区间，而前面合并不到
if(it->col==v) r=it->r,Upd2(r,-1),s.erase(it);
s.insert({l,r,v});
isR[r]=1,Upd2(r,1);
}
else if(op==3)
{
int l=rd(),r=rd(),ans=qsum(l,r);
if(!isR[r]) ans+=min(a[r],a[r+1])*w[r];
if(!isR[l-1]) ans+=min(a[l],a[l-1])*w[l];
printf("%lld\n",ans);
}
}
}
T4 扌非 歹刂
原 agc_038_f，有一点不同。
对于一个位置，如果选择移动，那么整个置换环都会移动。
记 \(x(i)\) 表示 \(A\) 中 \(i\) 所在的环是否移动，\(y(i)\) 表示 \(B\) 中 \(i\) 所在的环是否移动。
对于每一位，分类讨论。
- \(A_i=B_i=i\)，怎么整都没有用，直接令 \(ans+1\)。
- \(A_i\neq i,B_i=i\)，当且仅当移动 \(x(i)\) 答案不加 1。
- \(A_i=i,B_i\neq i\)，类似情况 2。
- \(A_i=B_i\neq i\)，当且仅当 \(x(i) \operatorname{xor} y(i)=1\) 答案不加 1。
- \(A_i\neq B_i,A_i \neq i,B_i \neq i\)，当且仅当 \(x(i) \operatorname{or} y(i)=1\) 答案不加 1。
注意每个置换环有两种情况，旋转或不旋转，容易想到建立网络流模型，转化为最小割问题。
令 \(a\) 表示 \(A\) 中环的结点，\(b\) 表示 \(B\) 中环的结点，\((u,v,w)\) 表示 \(u\) 向 \(v\) 连了边权为 \(w\) 的边。
若 \(a\) 分入 \(S\) 集合表示旋转，\(b\) 分入 \(T\) 集合表示不转。
- 割掉 \(S \rightarrow a\)，代价为情况 2 的个数。
- 割掉 \(b \rightarrow T\)，代价为情况 3 的个数。
- 对于情况 4，连边 \((a,b,1),(b,a,1)\)，如果割掉，表示 \(a,b\) 在不同集合，那么表示要么都旋，要么都不旋，代价为 1。
- 对于情况 5，连边 \((b,a,1)\)，如果割掉，表示 \(a\) 分在集合 \(T\)，\(b\) 分在集合 \(S\)，是都不选的情况，代价为 1。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,ans,S,T=1;
int tot=1,pre[N*2],cur[N*2],lv[N*2];
int cnt1=1,cnt2,p[N],q[N],hp[N],hq[N],wp[N],wq[N];
struct edge{int to,nxt,w;} e[N*8];
void add(int u,int v,int w)
{
e[++tot]={v,pre[u],w};pre[u]=tot;
e[++tot]={u,pre[v],0};pre[v]=tot;
}
int bfs()
{
memset(lv,0,sizeof(lv));
memcpy(cur,pre,sizeof(cur));
queue<int> q;q.push(S);lv[S]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=pre[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].w;
if(w>0&&!lv[v]) lv[v]=lv[u]+1,q.push(v);
}
}
return lv[T];
}
int dfs(int u=S,int flow=1e9)
{
if(u==T) return flow;
int lev=flow;
for(int i=cur[u];i&&lev;i=e[i].nxt)
{
cur[u]=i;
int v=e[i].to,w=e[i].w;
if(w>0&&lv[v]==lv[u]+1)
{
int out=dfs(v,min(lev,w));
lev-=out,e[i].w-=out,e[i^1].w+=out;
}
}
return flow-lev;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++) cin>>q[i];
for(int i=1;i<=n;i++) if(!hp[i]) {hp[i]=++cnt1;for(int j=p[i];j!=i;j=p[j]) hp[j]=cnt1;}cnt2=cnt1;
for(int i=1;i<=n;i++) if(!hq[i]) {hq[i]=++cnt2;for(int j=q[i];j!=i;j=q[j]) hq[j]=cnt2;}
for(int i=1;i<=n;i++)
{
if(p[i]==q[i]&&p[i]==i) ans++;
if(p[i]==i&&q[i]!=i) wq[hq[i]]++;
if(p[i]!=i&&q[i]==i) wp[hp[i]]++;
if(p[i]!=i&&q[i]!=i&&p[i]!=q[i]) add(hq[i],hp[i],1);
if(p[i]!=i&&q[i]!=i&&p[i]==q[i]) add(hp[i],hq[i],1),add(hq[i],hp[i],1);
}
for(int i=2;i<=cnt1;i++) if(wp[i]) add(S,i,wp[i]);
for(int i=cnt1+1;i<=cnt2;i++) if(wq[i]) add(i,T,wq[i]);
while(bfs()) ans+=dfs();
cout<<ans<<'\n';
}