题解：P7607 [THUPC 2021] 赌徒问题

想了很久自己为什么跑这么慢，结果发现是完全背包多写了一个

n

，没有人类了。

考虑枚举

s

，然后每次要做一个完全背包，可以获得一个

O(nm^3)

的做法。

看起来不太好优化，但是考虑到这里可能有很多数被重复加入删除，可以想到对于所有

(i,j)

连边，边权是从

s=i

到

s=j

需要修改的物品个数，然后跑一个最小生成树，记边权和为

w

，那么后面部分复杂度可以做到

O(nmw)

。发现

m=2000

的时候

w=8006

，可以轻松通过。

最后说一下怎么求 MST。发现只保留

(i,ki)(k\in \mathbb Z)

的边也是可以的，边权可以

O(m)

或者

O(\frac{m}w)

计算，那求 MST 的复杂度就是

O(\frac{m^2\log n}w)

。

CPP

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n,m,k,ans,f[12][2005],fd[2005],tot;
bitset<2005> vis,e[2005];
int find(int x){
	return fd[x]?fd[x]=find(fd[x]):x;
}
struct edge{
	int u,v,w;
	bool operator <(edge &x) const{
		return w<x.w;
	}
}ed[50005];
vector<int> g[2005];
inline void add(int x){
	if(vis[x]) return ;
	vis[x]=1;
	for(int i=0;i<n;i++)
		for(int k=0;k+x<=m;k++)
			f[i+1][k+x]=(f[i+1][k+x]+f[i][k])%mod;
}
inline void del(int x){
	if(!vis[x]) return ;
	vis[x]=0;
	for(int i=n-1;~i;i--)
		for(int k=0;k+x<=m;k++)
			f[i+1][k+x]=(f[i+1][k+x]-f[i][k])%mod;
}
void dfs(int x,int fa){
	for(int i=1;i<=m;i++)
		if(1ll*k*x%i==0)
			add(i);
	ans=(ans+f[n][x])%mod;
	for(int v:g[x])
		if(v^fa){
			int g[12][2005];
			bitset<2005> nw=vis;
			memcpy(g,f,sizeof(g));
			for(int i=1;i<=m;i++)
				if(1ll*k*x%i==0&&1ll*k*v%i)
					del(i);
			dfs(v,x);
			memcpy(f,g,sizeof(f)),vis=nw;
		}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>k;
//	n=10,m=2000,k=440000000;
	vis=0;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			e[i][j]=(1ll*i*k%j==0);
	for(int i=1;i<=m;i++)
		for(int j=i+i;j<=m;j+=i)
			ed[++tot]={i,j,(e[i]^e[j]).count()};
	sort(ed+1,ed+tot+1);
	int all=0;
	for(int i=1;i<=tot;i++){
		int u=ed[i].u,v=ed[i].v;
		if(find(u)==find(v)) continue;
		all+=ed[i].w,g[u].push_back(v),g[v].push_back(u);
		fd[find(u)]=find(v);
	}
	cerr<<all<<'\n';
	f[0][0]=1;
	dfs(1,0);
	cout<<ans<<'\n';
	return 0;
}

题解：P7607 [THUPC 2021] 赌徒问题

文章操作

相关推荐

评论

题解：P7607 [THUPC 2021] 赌徒问题