20251105 NOIP 模擬賽

Problem A. Graph

Description

構造一張競賽圖 \(G\)，進行 \(m\) 次翻轉邊的操作，要使得 \(G\) 任意時刻不強聯通。

\(6\le n\le 400\)。

Sub1：\(m\le n-2\)，Sub2：\(m\le \lceil\frac {3n} 2 \rceil-3\)，Sub3：\(m\le 2n-11\)。

Solution

Sub1：把 \(m\) 條邊建出來，圖一定不連通。拿出一個連通塊，放進 \(S\) 中，其余放進 \(T\) 中，只要讓 \(S\) 的邊全部指向 \(T\) 就行了，其他邊都不重要。

Sub2：找到一個點放入 \(S\)，其余都在 \(T\) 中。按時間遍歷翻轉邊，若這條邊連接了 \(S,T\)，就把 \(T\) 中那個點拿到 \(S\) 中，設為 \(x\)，然后再給 \(x\) 與 \(T\) 中其他邊欽定方向，使得它們此時都指向 \(x\)；若連接同一個集合就忽略。

這樣任意時刻 \(T\) 的邊都指向 \(S\)，最后 \(T\) 非空就合法。

給每個點記錄一下什么時候第一次被翻轉，取最晚的那個點就行。前面至少有 \(\lceil \frac n 2 \rceil-1\) 條邊被忽略。

Sub3：以時間為邊權找出最小生成樹，找到最晚的邊，將第一個點選在較小的那一邊就可以讓最大的那一邊全部被忽略。一直做下去，直到只剩一個點，可以忽略 \(n-1-\lfloor \log_2 n\rfloor\) 條邊。

int n,m;
bool vis[N];
int U[N<<1],V[N<<1];
int ans[N][N];
int cnt[N][N];

signed main(){
	read(n),read(m);
	for(int i=1;i<=m;i++) read(U[i]),read(V[i]);
	int Rt=0;
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		vis[i]=1;
		for(int j=1;j<=m;j++){
			vis[V[j]]|=vis[U[j]];
			vis[U[j]]|=vis[V[j]];
		}
		bool ok=0;
		for(int j=1;j<=n;j++)
			if(!vis[j]) ok=1;
		if(ok){
			Rt=i;
			break;
		}
	}
	memset(vis,0,sizeof(vis));
	vis[Rt]=1;
	for(int i=1;i<Rt;i++) ans[i][Rt]=1;
	for(int i=Rt+1;i<=n;i++) ans[Rt][i]=0;
	for(int i=1;i<=m;i++){
		int u=U[i],v=V[i];
		++cnt[u][v],++cnt[v][u];
		if(vis[u]==vis[v]) continue;
		if(vis[v]) swap(u,v);
		vis[v]=1;
		for(int x=1;x<=n;x++){
			if(vis[x]) continue;
			if(cnt[x][v]&1){
				if(v<x) ans[v][x]=1;
				else ans[x][v]=0;
			}
			else{
				if(x<v) ans[x][v]=1;
				else ans[v][x]=0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++)
			printf("%d ",ans[i][j]);
		puts("");
	}
	return 0;
}

Problem B. Gcds

Description

給定長為 \(n\) 的正整數序列 \(a\)，求可以修改其中的任意一個元素，使它變為的任意一個 \(\le m\) 正整數時，它的 \(\gcd>1\) 的子串個數的最大值。

\(n\le 5\times 10^4,a_i\le m\le 5\times 10^5\)。

Solution

枚舉修改位置 \(x\)，子串分為四部分：與 \(x\) 無交；以 \(x\) 為右端點；以 \(x\) 為左端點；跨過 \(x\)。

第一種與 \(a_x\) 的值無關，預處理；第二、三種需要分別在 \(a_{x-1},a_{x+1}\) 中選擇一個質因子；第四種需要選擇一個 \(\gcd(a_{x-1},a_{x+1})\) 的因子。

而第四種的因子有重復質因子一定不優，所以只需要枚舉質因子集合的子集。

枚舉子集，枚舉兩邊的質因子，這個看似是 \(O(2^{\omega}\omega^2)\) 的，但實際上界只有 \(144\)。

算答案時，兩邊的前后綴 \(\gcd\) 只有 \(\log V\) 種。第四種預處理子集和，第二、三種直接暴力統計，\(O(\log V)\)。

在一開始就可以把每個數的重復質因子去掉，把 \(\log V\) 降為 \(\omega\)。復雜度 \(O(n2^{\omega}\omega ^3)\)，跑不滿。

int n,a[N];
bool vis[M];
#define prev sbzcz
int prm[M],mnp[M],tot;
ll prev[N],sufv[N];
int msk[M],lg[K];
ll sum[K],prd[K];

struct Node{
	int x,w;
};
vector<Node> pre[N],suf[N];

const int V=500000;

void Init(){
	mnp[1]=1;
	for(int i=2;i<=V;i++){
		if(!vis[i]){
			mnp[i]=i;
			prm[++tot]=i;
		}
		for(int j=1;j<=tot;j++){
			if(i*prm[j]>V) break;
			vis[i*prm[j]]=1,mnp[i*prm[j]]=prm[j];
			if(i%prm[j]==0) break;
		}
	}
}

int Unique(int x){
	int y=1;
	while(x>1){
		y*=mnp[x];
		int z=mnp[x];
		while(x%z==0) x/=z;
	}
	return y;
}

void Workpre(){
	for(int i=1;i<=n;i++){
		pre[i].reserve(6);
		for(auto j:pre[i-1]){
			int x=__gcd(j.x,a[i]);
			if(x==1) continue;
			if(pre[i].size()&&pre[i].back().x==x) pre[i].back().w+=j.w;
			else pre[i].push_back(Node{x,j.w});
		}
		if(a[i]!=1){
			if(pre[i].size()&&pre[i].back().x==a[i]) ++pre[i].back().w;
			else pre[i].push_back(Node{a[i],1});
		}
		prev[i]=prev[i-1];
		for(auto j:pre[i]) prev[i]+=j.w;
	}	
}

void Worksuf(){
	for(int i=n;i;i--){
		suf[i].reserve(6);
		for(auto j:suf[i+1]){
			int x=__gcd(j.x,a[i]);
			if(x==1) continue;
			if(suf[i].size()&&suf[i].back().x==x) suf[i].back().w+=j.w;
			else suf[i].push_back({x,j.w});
		}
		if(a[i]!=1){
			if(suf[i].size()&&suf[i].back().x==a[i]) ++suf[i].back().w;
			else suf[i].push_back({a[i],1});
		}
		sufv[i]=sufv[i+1];
		for(auto j:suf[i]) sufv[i]+=j.w;
	}
}

vector<int> Divide(int x){
	vector<int> s;
	while(x>1){
		s.push_back(mnp[x]);
		x/=mnp[x];
	}
	return s;
}

ll Solve0(int x){
	ll res=0;
	for(auto i:pre[x-1]) res+=i.w;
	for(auto i:suf[x+1]) res+=i.w;
	for(auto i:pre[x-1])
		for(auto j:suf[x+1])
			if(__gcd(i.x,j.x)>1) res+=1ll*i.w*j.w;
	return res+prev[x-1]+sufv[x+1]+1;
}

ll Solve(int x){
	vector<int> p,sl,sr;
	int g=__gcd(a[x-1],a[x+1]);
	p=Divide(g);
	sl=Divide(a[x-1]/g);
	sr=Divide(a[x+1]/g);
	sl.push_back(1),sr.push_back(1);
	int siz=p.size(),AS=(1<<siz)-1;
	for(auto i:pre[x-1]){
		msk[i.x]=0;
		for(int j=0;j<siz;j++)
			if(i.x%p[j]==0) msk[i.x]|=(1<<j);
	}
	for(auto i:suf[x+1]){
		msk[i.x]=0;
		for(int j=0;j<siz;j++)
			if(i.x%p[j]==0) msk[i.x]|=(1<<j);
	}
	for(int i=0;i<=AS;i++) sum[i]=0;
	for(auto i:pre[x-1]){
		for(auto j:suf[x+1])
			sum[msk[i.x]&msk[j.x]]+=1ll*i.w*j.w;
	}
	for(int i=0;i<siz;i++){
		for(int s=0;s<=AS;s++)
			if(!(s>>i&1))
				sum[s|(1<<i)]+=sum[s];
	}
	ll ans=0;
	for(int s=0;s<=AS;s++){
		ll res=sum[AS]-sum[AS^s];
		if(s==0) prd[s]=1;
		else prd[s]=prd[s^(s&-s)]*p[__lg(s&-s)];
		for(int i:sl){
			for(int j:sr){
				if(1ll*prd[s]*i*j>500000) continue;
				ll val=0;
				for(auto k:pre[x-1]){
					if((msk[k.x]&s)||(i!=1&&!(k.x%i)))
						val+=k.w;
				}
				for(auto k:suf[x+1]){
					if((msk[k.x]&s)||(j!=1&&!(k.x%j)))
						val+=k.w;
				}
				Ckmax(ans,res+val);
			}
		}
	}
	ans+=prev[x-1]+sufv[x+1]+1;
	return ans;
}

signed main(){
	Init();
	read(n);
	for(int i=2;i<=(1<<6);i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++){
		read(a[i]);
		a[i]=Unique(a[i]);
	}
	Workpre(); Worksuf();
	a[0]=a[n+1]=1;
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(a[i-1]==a[i+1]) Ckmax(ans,Solve0(i));
		else Ckmax(ans,Solve(i));
	}
	printf("%lld\n",ans);
	return 0;
}

Problem D. Perm

Description

給定排列 \(A,B\)，求排列 \(C\) 的數量滿足 \(C_i\ne A_i\land C_i\ne B_i\)。\(n\le 3000\)。

Solution

\(A_i\) 向 \(B_i\) 連邊，會連出若干個環。

容斥，欽定 \(j\) 個位置不合法，其余任意。這些位置要么選 \(A_x\)，要么選 \(B_x\)，相當于在環上每個位置可以不選，可以選自己，可以選擇下一個點，但每個點不能被重復選。

對每個環做一遍 DP，每做完一個環就做一遍加法卷積。復雜度 \(O(n^2)\)。

int n,a[N],b[N],p[N];
ll f[N][N][2],g[N][N],fac[N];
bool vis[N];

const ll mod=1e9+7;

inline ll Mod(ll x){return (x>=mod)?(x-mod):(x);}
inline void Add(ll &x,ll y){x=Mod(x+y);}

void Work(int m){
	for(int i=2;i<=m;i++){
		for(int j=0;j<i;j++){
			Add(f[i][j][0],f[i-1][j][0]);
			Add(f[i][j+1][0],f[i-1][j][0]);
			Add(f[i][j+1][1],f[i-1][j][0]);
			Add(f[i][j][0],f[i-1][j][1]);
			Add(f[i][j+1][1],f[i-1][j][1]);
		}
	}
}

void Solve(){
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	memset(vis,0,sizeof(vis));
	read(n);
	fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]),p[a[i]]=b[i];
	g[0][0]=1; int m=0;
	for(int x=1;x<=n;x++){
		if(vis[x]) continue;
		int siz=0,y=x; ++m;
		while(!vis[y]){
			++siz; vis[y]=1;
			y=p[y];
		}
		if(siz==1){
			for(int i=0;i<=n;i++){
				g[m][i]=g[m-1][i];
				if(i) Add(g[m][i],g[m-1][i-1]);
			}
			continue;
		}
		for(int j=0;j<=siz;j++)
			for(int k=0;k<=siz;k++)
				f[j][k][0]=f[j][k][1]=0;
		f[1][0][0]=f[1][1][1]=1; Work(siz);
		for(int i=0;i<=n;i++){
			for(int j=0;j<=min(i,siz);j++)
				(g[m][i]+=g[m-1][i-j]*(f[siz][j][0]+f[siz][j][1]))%=mod;
		}
		for(int j=0;j<=siz;j++)
			for(int k=0;k<=siz;k++)
				f[j][k][0]=f[j][k][1]=0;
		f[1][1][0]=1; Work(siz);
		for(int i=0;i<=n;i++){
			for(int j=0;j<=min(i,siz);j++)
				(g[m][i]+=g[m-1][i-j]*f[siz][j][0])%=mod;
		}
	}
	ll ans=0;
	for(int i=0;i<=n;i++){
		ll res=g[m][i]*fac[n-i]%mod;
		if(i&1) (ans+=mod-res)%=mod;
		else (ans+=res)%=mod;
	}
	printf("%lld\n",ans);
}

signed main(){
	int T; read(T);
	while(T--) Solve();
	return 0;
}