Is that a kind of fetishism?

No, he is objectively a god.

见识了一把 Mcdic 究竟出题有多神。

（虽然感觉还是吹过头了）

开了场 Virtual 玩。

开场先秒了 AB。C 居然差点没做出来，有点耻辱。

开 D。怎么不会……Div. 2 的 D 都能卡住我，我心态崩了。

调到 E。 woc 这不是 sb 题吗……

回来肝 D。想了想口胡出来了，然而心态已经崩了，用了很长很长时间才打出来。

最后只剩 20min 时开 F。这……辣鸡三合一？不管了。

---

A

暴力模拟即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=100010;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int l,r,cnt[10];

bool check(int x){

	while(x) cnt[x%10]++,x/=10;

	bool ans=true;

	FOR(i,0,9) if(cnt[i]>=2) ans=false;

	FOR(i,0,9) cnt[i]=0;

	return ans;

}

int main(){

	l=read();r=read();

	FOR(i,l,r) if(check(i)) return printf("%d\n",i),0;

	puts("-1");

}

B

发现第 \(i\) 行最左边 \(\min(a_i+1,m)\) 列是已经确定要填什么的，第 \(i\) 列最上面 \(\min(b_i+1,n)\) 行是已经确定要填什么的。剩下的任意。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=1111,mod=1000000007;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int n,m,ans=1,mat[maxn][maxn];

int main(){

	n=read();m=read();

	FOR(i,1,n) FOR(j,1,m) mat[i][j]=-1;

	FOR(i,1,n){

		int x=read();

		FOR(j,1,x){

			if(mat[i][j]==0) return puts("0"),0;

			mat[i][j]=1;

		}

		if(x!=m){

			if(mat[i][x+1]==1) return puts("0"),0;

			mat[i][x+1]=0;

		}

	}

	FOR(j,1,m){

		int x=read();

		FOR(i,1,x){

			if(mat[i][j]==0) return puts("0"),0;

			mat[i][j]=1;

		}

		if(x!=n){

			if(mat[x+1][j]==1) return puts("0"),0;

			mat[x+1][j]=0;

		}

	}

//	FOR(i,1,n){

//		FOR(j,1,m) printf("%d ",mat[i][j]);

//		puts("");

//	}

	FOR(i,1,n) FOR(j,1,m) if(mat[i][j]==-1) ans=2ll*ans%mod;

	printf("%d\n",ans);

}

C

考虑每个质因数的贡献，做完了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=100010,mod=1000000007;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int x,num[maxn],len,ans=1;

ll n;

int calc(int x){

	int ans=0;

	ll pr=x;

	while(true){

		ans=(ans+n/pr)%(mod-1);

		ll pre=pr;

		pr*=x;

		if(pr/pre!=x || pr>n) break;

	}

	return ans;

}

int qpow(int a,int b){

	int ans=1;

	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;

	return ans;

}

int main(){

	x=read();n=read();

	for(int i=2;i*i<=x;i++) if(x%i==0){

		num[++len]=i;

		while(x%i==0) x/=i;

	}

	if(x>1) num[++len]=x;

	FOR(i,1,len){

		int x=num[i];

		ans=1ll*ans*qpow(x,calc(x))%mod;

	}

	printf("%d\n",ans);

}

D

说实话，挺神仙的。

图不连通时，明显无解。

从点集 1，点集 2，点集 3 中分别任选一个点，肯定两两有连边。

不妨先在图中随便找到一个三元环，上面的三个点肯定是一个点集 1，一个点集 2，一个点集 3，顺序无关。如果没有三元环，无解。

对于剩下的每个点 \(u\)，如果 \(u\) 和这三点其中某个点没有连边，说明它们肯定在一个点集中。如果和这三个点中多个点都没有连边，无解。

最后 check 一波。

时间复杂度 \(O(n)\)

upd：看了洛谷上一些人的题解，根本不用找三元环，直接钦定一个点在点集 1，与这个点不是一个点集的某个点是 2。应该会好写很多。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=600060;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int n,m,el,head[maxn],to[maxn],nxt[maxn],u_fa[maxn],dep[maxn],fa[maxn],ans[maxn],q[maxn],h,r,cnt=0;

bool flag,nnn[4],vis[maxn],use[maxn];

inline void add(int u,int v){

	to[++el]=v;nxt[el]=head[u];head[u]=el;

}

int getfa(int x){

	return x==u_fa[x]?x:u_fa[x]=getfa(u_fa[x]);

}

void dfs(int u,int f){

	dep[u]=dep[f]+1;fa[u]=f;

	for(int i=head[u];i;i=nxt[i]){

		int v=to[i];

		if(v==f) continue;

		if(dep[v]){

			if(fa[fa[u]]==v && !flag){

				ans[u]=1;ans[fa[u]]=2;ans[fa[fa[u]]]=3;

				flag=true;

			}

		}

		else dfs(v,u);

	}

}

void dfs2(int u,int f,int x,int y){

	vis[u]=true;

	for(int i=head[u];i;i=nxt[i]){

		int v=to[i];

		if(v==f || (ans[v]!=x && ans[v]!=y)) continue;

		if(!use[(i+1)/2]) cnt++,use[(i+1)/2]=true;

		if(!vis[v]) dfs2(v,u,x,y);

	}

}

bool check(int x,int y){

	MEM(vis,0);

	int cnt1=0,cnt2=0;

	FOR(i,1,n){

		if(ans[i]==x) cnt1++;

		if(ans[i]==y) cnt2++;

	}

	cnt=0;

	FOR(i,1,n) if(ans[i]==x){dfs2(i,0,x,y);break;}

	return 1ll*cnt1*cnt2==cnt;

}

int main(){

	n=read();m=read();

	FOR(i,1,n) u_fa[i]=i;

	FOR(i,1,m){

		int u=read(),v=read();

		add(u,v);add(v,u);

		u=getfa(u);v=getfa(v);

		u_fa[u]=v;

	}

	FOR(i,1,n) if(getfa(i)!=getfa(1)) return puts("-1"),0;

	dfs(1,0);

	if(!flag) return puts("-1"),0;

	FOR(u,1,n){

		if(ans[u]) continue;

		nnn[1]=nnn[2]=nnn[3]=false;

		for(int i=head[u];i;i=nxt[i]){

			int v=to[i];

			if(ans[v]) nnn[ans[v]]=true;

		}

		FOR(i,1,3) if(!nnn[i]){

			if(ans[u]) return puts("-1"),0;

			ans[u]=i;

		}

		if(!ans[u]) return puts("-1"),0;

	}

	if(!check(1,2) || !check(1,3) || !check(2,3)) return puts("-1"),0;

	FOR(i,1,n) printf("%d ",ans[i]);

}

E

简单二项式反演。

先特判 \(k=1\)。下文假设 \(k\ge 2\)。

设 \(f_{i,j}\) 是恰好 \(i\) 行不满足要求，恰好 \(j\) 列不满足要求的方案数。要求是 \(f_{0,0}\)。

设 \(g_{i,j}\) 是对于所有方案中，选出 \(i\) 行不满足要求，\(j\) 列不满足要求的方案数之和。很明显有 \(g_{i,j}=\binom{n}{i}\binom{n}{j}(k-1)^{n^2-(n-i)(n-j)}k^{(n-i)(n-j)}\)。

根据定义，\(g_{i,j}=\sum\limits_{x=i}^n\sum\limits_{y=j}^n\binom{x}{i}\binom{y}{j}f_{x,y}\)。

二项式反演，\(f_{i,j}=\sum\limits_{x=i}^n\sum\limits_{y=j}^n\binom{x}{i}\binom{y}{j}(-1)^{(x-i)+(y-j)}g_{x,y}\)。

时间复杂度 \(O(n^2\log n)\)。可以进一步优化，但是没必要了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> PII;

const int maxn=100010,mod=1000000007;

#define MP make_pair

#define PB push_back

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline ll read(){

	char ch=getchar();ll x=0,f=0;

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

int n,k,ans,fac[maxn],invfac[maxn];

int qpow(int a,ll b){

	int ans=1;

	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;

	return ans;

}

int C(int n,int m){

	return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;

}

int main(){

	n=read();k=read();

	if(k==1) return puts("1"),0;

	fac[0]=1;

	FOR(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;

	invfac[n]=qpow(fac[n],mod-2);

	ROF(i,n-1,0) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;

	FOR(i,0,n) FOR(j,0,n){

		int sum=1ll*C(n,i)*C(n,j)%mod*qpow(k-1,1ll*n*n-1ll*(n-i)*(n-j))%mod*qpow(k,1ll*(n-i)*(n-j))%mod;

//		printf("i=%d,j=%d,sum=%d\n",i,j,sum);

		if((i+j)%2==0) ans=(ans+sum)%mod;

		else ans=(ans-sum+mod)%mod;

	}

	printf("%d\n",ans);

}

F

在路上了。