Atcoder Regular Contest 107 题解（A-F）
Pro A Simple Math
-
题意：给定 (a,b,c) ，求 (sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}sumlimits_{k=1}^{c}i imes j imes kpmod{998244353}) 的值。
-
数据范围：(1leq a,b,cleq10^9)
-
做法：
简单的提取公因式可得原式等价于求 (sumlimits_{i=1}^{a}isumlimits_{j=1}^{b}jsumlimits_{k=1}^{c}k) 。
-
代码：
const int Mod=998244353; int a,b,c; int main(){ r(a,b,c); a=(1ll*(a+1)*a/2)%Mod; b=(1ll*(b+1)*b/2)%Mod; c=(1ll*(c+1)*c/2)%Mod; w(1ll*a*b%Mod*c%Mod); return 0; }
Pro B Quadruple
-
题意：给定 (n,k) ，求有多少有序四元组 ((a,b,c,d)) ，满足 (1leq a,b,c,dleq n,a+b-c-d=k) 。
-
数据范围：(1leq nleq 10^5,-2(n-1)leq kleq 2(n-1))
-
做法：
首先可以发现等于 (k) 和等于 (-k) 的方案是一样的。我们把四元组看成两部分，分别是两个数的和。于是求出 (forall iin[2,2n],a+b=i) 的二元组 ((a,b)) 的方案就可以了。
-
代码：
const int N=2e5+5; using namespace std; int n,k,t[N]; long long ans; int main(){ r(n,k); k=abs(k); for(int i=2;i<=n+1;++i) t[i]=t[2*n-i+2]=i-1; for(int i=k+2;i<=2*n;++i) ans+=1ll*t[i]*t[i-k]; w(ans); return 0; }
Pro C Shuffle Permutation
-
题意：给一个 (n imes n) 的矩阵 (a) 和正整数 (k) 。Sigma 每次刻意任意选择下述一种操作来变换这个矩阵：（1）选择两个数 (x,y) ，满足 (forall iin [1,n] a_{x,i}+a_{y,i}leq k) ，交换这两行；（2）选择两个数 (x,y) ，满足 (forall iin[1,n] a_{i,x}+a_{i,y}leq k) ，交换这两列。请问 Sigma 总共可以获得多少种本质不同的矩阵。
-
(1leq nleq 50,1leq kleq 2 imes n^2,a_{i,j}) 保证是 (1sim n^2) 的一种重排
-
做法：
首先，由于 (a_{i,j}) 保证是 (1sim n^2) 的一种重排，所以只要在两次变换中，存在任意一个操作只在两次变换中的一个出现时，得到的两个矩阵就是必然不同的。进一步观察发现，如果第 (i,j) 行可以交换，第 (j,k) 行可以交换，那么这三行的位置是可以任意重排的，对于列而言也是如此。同时，当交换任意两行时，是不会改变列的可换的方案的。所以我们分别用并查集维护行和列就行了。
const int N=55,Mod=998244353; using namespace std; int n,m,ans=1; int f[N],fac[N],siz[N],a[N][N]; int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);} int main(){ scanf("%d%d",&n,&m); fac[0]=1; for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%Mod; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]); for(int i=1;i<=n;++i) f[i]=i; for(int i=1;i<=n-1;++i) for(int j=i+1;j<=n;++j){ bool flag=true; for(int k=1;k<=n&&flag;++k) if(a[i][k]+a[j][k]>m) flag=false; if(flag) f[Find(i)]=Find(j); } for(int i=1;i<=n;++i) siz[Find(i)]++; for(int i=1;i<=n;++i) ans=1ll*fac[siz[i]]*ans%Mod; for(int i=1;i<=n;++i) f[i]=i,siz[i]=0; for(int i=1;i<=n-1;++i) for(int j=i+1;j<=n;++j){ bool flag=true; for(int k=1;k<=n&&flag;++k) if(a[k][i]+a[k][j]>m) flag=false; if(flag) f[Find(i)]=Find(j); } for(int i=1;i<=n;++i) siz[Find(i)]++; for(int i=1;i<=n;++i) ans=1ll*fac[siz[i]]*ans%Mod; printf("%d ",ans); return 0; }
Pro D Number of Multisets
-
题意：给定 (n,k) ，问有多少种选出 (n) 个数的方案，满足 (n) 个数的和为 (k) 。这 (n) 个数都须是 (frac{1}{2^{i}}(iin[0,infin))) 的形式。
-
范围：(1leq kleq nleq 3 imes 10^3)
-
做法：
当前处理的问题为选出 (n) 个数满足和为 (k) 。我们记这个的方案数为 (f(n,k)) 。我们可以把这个方案分成两类情况：
- 至少选择一个 (1) 。此时问题转化为求解 (f(n-1,k-1))
- 不选择 (1) 。此时问题转化为：问有多少种选出 (n) 个数的方案，满足 (n) 个数的和为 (k) 。这 (n) 个数都须是 (frac{1}{2^{i}}(iin[1,infin))) 的形式。我们考虑这个子问题的限制条件与原问题的限制条件的关系。如果我们将这 (n) 个数同时乘以二，那么子问题的限制条件就和原问题的限制条件一致了。此时问题转化为求解 (f(n,2k))
边界条件：(f(n,k)=0(n<k),f(n,0)=[n=0])
-
代码：
const int N=3e3+5,Mod=998244353; using namespace std; int f[N][N]; int solve(int n,int k){ if(n<=k) return n==k; if(k==0) return 0; if(f[n][k]!=-1) return f[n][k]; return f[n][k]=(solve(n-1,k-1)+solve(n,2*k))%Mod; } int main(){ int n,k;r(n,k); memset(f,-1,sizeof f); w(solve(n,k)); return 0; }
Pro E Mex Mat
-
题意：给定一个 (n imes n) 的矩阵 (a) 的第一行和第一列，(a_{i,j}= ext{mex}(a_{i-1,j},a_{i,j-1})(i,jgeq 2)) 。第一行和第一列中只有 (0,1,2) ，求这个矩阵中 (0,1,2) 的个数。
-
数据范围：(1leq nleq 5 imes 10^5)
-
做法：
( ext{mex}) 这个函数挺玄学的。我们打表可以发现，当 (nge 4) 后，恒有 (a_{i,j}= a_{i-1,j-1}(i,jge 4)) 。
-
代码：
const int N=5e5+5; using namespace std; const int mex[3][3]={{1,2,1},{2,0,0},{1,0,0}}; int n; int a[N],b[N]; long long c[3]; void run(int x){ for(int i=2;i<=x;++i){ a[i-1]=b[i]; for(int j=i;j<=n;++j) a[j]=mex[a[j-1]][a[j]],++c[a[j]]; b[i]=a[i]; for(int j=i+1;j<=n;++j) b[j]=mex[b[j-1]][b[j]],++c[b[j]]; } } int main(){ r(n); for(int i=1;i<=n;++i) r(a[i]),++c[a[i]]; for(int i=2;i<=n;++i) r(b[i]),++c[b[i]]; if(n<=5) run(n); else{ run(5); for(int i=5;i<=n;++i) c[a[i]]+=n-i; for(int i=6;i<=n;++i) c[b[i]]+=n-i; } w(c[0],' '),w(c[1],' '),w(c[2],' '); return 0; }
Pro F Sum of Abs
-
题意：给定一张 (n) 个点 (m) 条边的无向图，每个点有两个值 (a_i,b_i) 。你可以选定一些点，每个点花费 (a_i) 的代价删除它（以及与它相连的）。你的获利是每个连通块的 (b_i) 的和的绝对值。你的收益是总获利减去总代价。求最大收益。
-
数据范围：(1leq n,mleq 300,1leq a_ileq 10^6,-10^6leq b_ileq 10^6) 图无重边无自环。
-
做法：
我们可以将绝对值拆为取 (max) ，于是某一个连通块贡献的权值可以写作 (max(sum b_i,sum -b_i)) 。所以，一个点 (u) 对于答案的贡献只为三种：(-a_u,b_u,-b_u) 。三个中选择一个，我们考虑最小割模型。设源点为 (s) ，汇点为 (t) ，我们将每个点 (u) 拆为 (u_0,u_1) ，并连边 (s ightarrow u_0 ightarrow u_1 ightarrow t) ，边权依次为 (-b_i,a_i,b_i) 。割去 (u) 的哪条边，就意味着点 (u) 的贡献形式（的负数）。
但是边 ((u,v)) 会对我们割边造成限制。如果我们不删去 (u,v) ，那么 (u,v) 的贡献必须同时为 (-b_i) 或者同时为 (b_i) 。针对这条限制，我们新建两条边，分别为 (u_1 ightarrow v_0,v_1 ightarrow u_0) ，边权均为 (infin) 。除了针对限制外，这两条边加的很有讲究：如果直接割去了 (u_0 ightarrow u_1) 或者割去了 (v_0 ightarrow v_1) ，那么这两条边必定无效，而这恰好也是我们所需要的。所以答案就是最小割的相反数。但是我们的边权中出现了负数，这是不能跑最大流的。故我们将每条非 (infin) 边都加上 ( ext{abs}(b_i)) 。复杂度 (mathcal{O}(n^2(n+m))) 。
-
代码：
const int N=6e2+5,M=3e3+5,INF=1e9; using namespace std; int n,m,s,t,ans,num=1; int a[N],b[N],d[N],head[N],nt[M],to[M],cap[M]; bool BFS(){ for(int i=s;i<=t;++i) d[i]=0; queue<int>q;q.push(s);d[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=nt[i]){ if(!cap[i]||d[to[i]]) continue; d[to[i]]=d[u]+1;q.push(to[i]); if(to[i]==t) return true; } } return false; } int dinic(int p,int flow){ if(p==t) return flow; int res=flow; for(int i=head[p];i&&res;i=nt[i]){ if(!cap[i]||d[to[i]]!=d[p]+1) continue; int k=dinic(to[i],min(cap[i],res)); if(!k) d[to[i]]=0; cap[i]-=k;cap[i^1]+=k;res-=k; } return flow-res; } void Add(int x,int y,int z){ ++num;nt[num]=head[x];head[x]=num;to[num]=y;cap[num]=z; ++num;nt[num]=head[y];head[y]=num;to[num]=x;cap[num]=0; } int main(){ r(n,m);s=0,t=n+n+1; for(int i=1;i<=n;++i) r(a[i]); for(int i=1;i<=n;++i) r(b[i]); for(int i=1;i<=n;++i){ ans+=abs(b[i]);Add(i,i+n,abs(b[i])+a[i]); if(b[i]>0) Add(s,i,b[i]+b[i]); else Add(i+n,t,-b[i]-b[i]); } for(int i=1,x,y;i<=m;++i) r(x,y),Add(x+n,y,INF),Add(y+n,x,INF); int Max=0,flow=0; while(BFS()) while(flow=dinic(s,INF)) Max+=flow; w(ans-Max); return 0; }