CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest15 [2021/08/15 19:24]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest15 [2021/08/27 21:42] (当前版本)
jxm2001
@@ 行 4: / 行 4: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
-|  A  |  0  |  0  |  0  |
+|  A  |  2  |  1  |  0  |
-|  B  |  0  |  0  |  0  |
+|  B  |  2  |  1  |  0  |
-|  C  |  2  |  0  |  0  |
+|  C  |  2  |  1  |  0  |
 |  D  |  0  |  0  |  0  |
 |  F  |  0  |  0  |  0  |
-|  G  |  0  |  0  |  0  |
+|  G  |  2  |  2  |  0  |
 |  I  |  1  |  0  |  2  |
 |  J  |  2  |  0  |  2  |
 ====== 题解 =====
+===== A. A Math Challenge =====
+==== 题意 ====
+$$
+\sum_{i=0}^n\sum_{1\le cj\le ai+b}i^pj^q
+$$
+==== 题解 ====
+设 $F(n)=\sum_{i=1}^n i^q$，于是上式转化为
+$$
+\sum_{i=0}^ni^pF(\lfloor \frac {ai+b}c\rfloor)
+$$
+由于 $F(n)$ 是 $q+1$ 次多项式，所以高斯消元可以暴力求出 $F(n)$ 的表达式。于是问题转化为计算 $\sum_{i=0}^ni^p(\lfloor \frac {ai+b}c\rfloor)^k(0\le k\le q)$。
+上式用万能欧几里得算法板子可以 $O\left(p^2q^2\log c\right)$，题目正解是类欧几里得算法 $O\left((p+q)^3\log c\right)$，不过卡卡常还是能过的。
+<hidden 查看代码>
+<code cpp>
+const int mod=998244353,MAXK=53;
+int C[MAXK][MAXK];
+struct Node{
+	int cntr,cntu,f[MAXK][MAXK];
+	Node(int cntr=0,int cntu=0){
+		this->cntr=cntr;
+		this->cntu=cntu;
+		mem(f,0);
+	}
+	Node operator * (const Node &b)const{
+		static int px[MAXK],py[MAXK];
+		static int b1[MAXK][MAXK],b2[MAXK][MAXK];
+		Node c;
+		int dx=cntr,dy=cntu;
+		px[0]=py[0]=1;
+		_for(i,1,MAXK)
+		px[i]=1LL*px[i-1]*dx%mod;
+		_for(i,1,MAXK)
+		py[i]=1LL*py[i-1]*dy%mod;
+		_for(i,0,MAXK)_rep(j,0,i){
+			b1[i][j]=1LL*C[i][j]*px[i-j]%mod;
+			b2[i][j]=1LL*C[i][j]*py[i-j]%mod;
+		}
+		c.cntr=(cntr+b.cntr)%mod;
+		c.cntu=(cntu+b.cntu)%mod;
+		_for(i,0,MAXK)_for(j,0,MAXK){
+			c.f[i][j]=f[i][j];
+			_rep(i2,0,i)_rep(j2,0,j)
+			c.f[i][j]=(c.f[i][j]+1LL*b.f[i2][j2]*b1[i][i2]%mod*b2[j][j2])%mod;
+		}
+		return c;
+	}
+};
+Node quick_pow(Node n,int k){
+	Node ans=Node(0,0);
+	while(k){
+		if(k&1)ans=ans*n;
+		k>>=1;
+		if(k)n=n*n;
+	}
+	return ans;
+}
+Node asgcd(int a,int b,int c,int n,Node su,Node sr){
+	if(a>=c)
+	return asgcd(a%c,b,c,n,su,quick_pow(su,a/c)*sr);
+	int m=(1LL*a*n+b)/c;
+	if(!m)
+	return quick_pow(sr,n);
+	else
+	return quick_pow(sr,(c-b-1)/a)*su*asgcd(c,(c-b-1)%a,a,m-1,sr,su)*quick_pow(sr,n-(1LL*c*m-b-1)/a);
+}
+Node cal(int a,int b,int c,int n){
+	Node su=Node(0,1),sr=Node(1,0);
+	_for(i,0,MAXK)
+	sr.f[i][0]=1;
+	return quick_pow(su,b/c)*asgcd(a,b%c,c,n,su,sr);
+}
+int a[MAXK][MAXK],pw[MAXK][MAXK],A[MAXK];
+void Init(){
+	C[0][0]=1;
+	_for(i,1,MAXK){
+		C[i][0]=1;
+		_rep(j,1,i)
+		C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
+	}
+	_for(i,0,MAXK){
+		pw[i][0]=1;
+		_for(j,1,MAXK)
+		pw[i][j]=1LL*pw[i][j-1]*i%mod;
+	}
+}
+int quick_pow(int n,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*n%mod;
+		n=1LL*n*n%mod;
+		k>>=1;
+	}
+	return ans;
+}
+void build(int n){
+	_for(i,0,n){
+		_for(j,0,n)
+		a[i][j]=pw[i][j];
+		_rep(j,1,i)
+		a[i][n]=(a[i][n]+pw[j][n-2])%mod;
+	}
+	_for(i,0,n){
+		int pos=-1;
+		_for(j,i,n){
+			if(a[j][i]){
+				pos=j;
+				break;
+			}
+		}
+		if(pos!=i)
+		swap(a[i],a[pos]);
+		int div=quick_pow(a[i][i],mod-2);
+		_rep(j,i,n)
+		a[i][j]=1LL*a[i][j]*div%mod;
+		_rep(j,0,n){
+			if(j==i)continue;
+			for(int k=n;k>=i;k--)
+			a[j][k]=(a[j][k]+mod-1LL*a[j][i]*a[i][k]%mod)%mod;
+		}
+	}
+	_for(i,0,n)
+	A[i]=a[i][n];
+}
+int main()
+{
+	Init();
+	int a=read_int(),b=read_int(),c=read_int(),p=read_int(),q=read_int(),n=read_int();
+	Node ans=cal(a,b,c,n);
+	int base=1;
+	_for(i,0,MAXK){
+		ans.f[0][i]=(ans.f[0][i]+base)%mod;
+		base=1LL*base*(b/c)%mod;
+	}
+	build(q+2);
+	int s=0;
+	_rep(i,0,q+1)
+	s=(s+1LL*ans.f[p][i]*A[i])%mod;
+	enter(s);
+	return 0;
+}
+</code>
+</hidden>
+===== B. Best Subgraph =====
+==== 题意 ====
+定义 $k-\text{degree}$ 子图为每个点在子图中度数至少为 $k$ 的连通极大子图。
+定义每个 $G$ 的子图 $S$ 的分数为 $M\times m(S)-N\times n(S)+B\times b(S)$。
+其中 $m(S)$ 表示 $S$ 的边数，$n(S)$ 表示 $S$ 的点数，$b(S)$ 表示 $|\{(u,v)|(u,v)\in G,u\in S,v\not\in S\}|$。
+求分数最大的 $k-\text{degree}$ 子图，并求出分数最大的 $k-\text{degree}$ 子图中 $k$ 的最大值。
+输入保证图连通。
+==== 题解 ====
+首先，定义 $V(k)$ 表示所有 $k-\text{degree}$ 子图的并集，易知 $V(k+1)\subseteq V(k)$。
+构建分层图，其中第 $k$ 层的点集为 $V(k)-V(k+1)$，同时对每个点 $u\in V(k)-V(k+1)$，$w(u)=k$。
+然后考虑按层加点，动态维护当前每个 $k-\text{degree}$ 子图的答案。对于每个新加入的点 $u$，首先他本身产生贡献 $-N$。
+对于 $u$ 的所有连边 $(u,v)$，如果 $w(v)\gt w(u)$，则 $(u,v)$ 会被加入 $m(S)$，同时从 $b(S)$ 删除，产生贡献 $M-B$。
+如果 $w(v)=w(u)$，则 $(u,v)$ 也会被加入 $m(S)$，但为了贡献被计算两次，于是每个点的贡献为 $\frac M2$。
+如果 $w(v)\lt w(u)$，则 $(u,v)$ 会被加入 $b(S)$，产生贡献 $B$。
+于是上述过程可以将所有贡献都转化为每个点的点权。考虑加入点时并查集维护每个连通块的点权和。
+每层点全部加完后查询每个连通块的点权和的最大值即为所有 $k-\text{degree}$ 子图的最大答案。
+至于如果计算每个点的 $w(u)$。首先输入保证图连通，所有图 $G$ 本身就是 $1-\text{degree}$ 子图。
+考虑先删去所有度数为 $1$ 的点，删点后可能会导致原来度数不为 $1$ 的点度数不大于 $1$，继续删除，直到无点可删，得到 $2-\text{degree}$ 子图。
+将删去的点的 $w(u)$ 全部设为 $1$，然后再求  $3-\text{degree}$ 子图不断重复上述过程，即可得到所有 $w(u)$。
+时间复杂度 $O\left(\text{Na}(n+m)\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+5;
+const LL inf=1e18;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+bool vis[MAXN];
+vector<int> q[MAXN],vec[MAXN];
+int deg[MAXN],w[MAXN],p[MAXN];
+LL sum[MAXN];
+int Find(int x){
+	return x==p[x]?x:p[x]=Find(p[x]);
+}
+int main()
+{
+	int n=read_int(),m=read_int(),M=read_int(),N=read_int(),B=read_int();
+	while(m--){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+		deg[u]++;
+		deg[v]++;
+	}
+	_rep(i,1,n)
+	q[deg[i]].push_back(i);
+	_for(k,1,MAXN){
+		_for(j,0,q[k].size()){
+			int u=q[k][j];
+			if(vis[u])continue;
+			vis[u]=true;
+			w[u]=k;
+			vec[k].push_back(u);
+			for(int i=head[u];i;i=edge[i].next){
+				int v=edge[i].to;
+				deg[v]--;
+				q[deg[v]].push_back(v);
+			}
+		}
+	}
+	_rep(u,1,n){
+		p[u]=u;
+		sum[u]=-N;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(w[u]<w[v]){
+				sum[u]+=M;
+				sum[u]-=B;
+			}
+			else if(w[u]==w[v]&&u<v)
+			sum[u]+=M;
+			else if(w[u]>w[v])
+			sum[u]+=B;
+		}
+	}
+	int st=MAXN-1;
+	while(vec[st].empty())st--;
+	pair<LL,int> ans=make_pair(-inf,0);
+	for(int k=st;k;k--){
+		for(int u:vec[k]){
+			for(int i=head[u];i;i=edge[i].next){
+				int v=edge[i].to;
+				if(w[v]<k)continue;
+				int x=Find(u),y=Find(v);
+				if(x!=y){
+					p[x]=y;
+					sum[y]+=sum[x];
+				}
+			}
+		}
+		for(int u:vec[k])
+		ans=max(ans,make_pair(sum[Find(u)],k));
+	}
+	space(ans.second);enter(ans.first);
+	return 0;
+}
+</code>
+</hidden>
 ===== C. Cells =====

CVBB ACM Team

用户工具

站点工具

页面工具