自动搬运

查看原文

来自洛谷，原作者为

	翼德天尊 2019-09-26 ~ 2024-03-03

搬运于2025-08-24 22:22:09，当前版本为作者最后更新于2020-06-06 09:05:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我又来啦QwQ!

一道很不错的联通块+推公式题。

STEP 1 解题大致思路

经过一段时间的思索，我们可以轻易地将这道题分成几个子任务：

1. 输入整张地图；

2. 遍历整张地图：

   • 找到座椅；

   • 进入 $dfs$ 遍历，找到这个联通块的所有座椅，并且记录有几个座椅周围只有一个座椅以及该联通块的座椅个数，注意遍历完的座椅要标记；

   • 如果该联通块周围有一个座椅的座椅不是两个且联通块个数不为 $1$，说明该图不合法，输出0并结束程序；

   • 否则根据联通块个数套入公式计算即可。

3. 将计算完的答案输出。

STEP 2 推导公式

当联通块合法的时候，我们可以对于这个联通块套用计算公式。

既然每一个合法的联通块都是“条形”座位，那么只要联通块合法，我们就完全可以将它掰成一个直的条形座位。

对于每一个条形的座位联通块，第一个座位一定可以放 $k$ 个学校的学生，也就是有 $k$ 种可能，而后面的座位因为前面的一个座位已经选过了一个学校，为了符合题意，只能放 $k-1$ 个学校的学生，所以若设联通块的座位个数为 $w$，则通项公式为：

然后我们把所有的联通块的可能性个数乘起来就好啦！（不要忘记驱魔哦QwQ）

STEP 3 $AC\ code$ 及注释

#include<bits/stdc++.h>
using namespace std;
#define inf 998244353//模数
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//每一项对应一个方向
int n,m,k,tot;//如题，如下
long long sum,ans=1;//如题，如下
char ma[1001][1001];//储存地图
long long ksm(long long s,long long mi){//快速幂加速
	long long ans=1,cnt=s;
	while (mi){
		if (mi&1) ans=ans*cnt%inf;
		cnt=cnt*cnt%inf;
		mi>>=1;
	}
	return ans;
} 
int find(int x,int y){//寻找周围的座椅数
	int js=0;
	for (int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&ma[xx][yy]!='X') js++;
	}
	return js;
}
void dfs(int x,int y){//简单dfs搜索
	if (find(x,y)==1) tot++;//记录周围只有一个座椅的座椅数
	ma[x][y]='W';//换一个标记以方便记录每个座椅周围的座椅数
	sum++;//座椅数++
	for (int i=0;i<4;i++){//四个方向遍历
		int xx=x+dx[i],yy=y+dy[i];
		if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&ma[xx][yy]=='O'){
			dfs(xx,yy);
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);//加速神器
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>ma[i][j];
		}
	}//输入地图
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){//遍历地图
			if (ma[i][j]=='O'){
				sum=tot=0;//初始化，sum记录座椅个数，tot记录周围只有一个座椅的座椅个数
				dfs(i,j);//dfs搜索
				if (tot<2&&sum>1){//不合法
					cout<<0<<endl;
					return 0;
				}
				ans=ans*k%inf*ksm(k-1,sum-1)%inf;//套公式
			}
		}
	}
	cout<<ans<<endl;//输出
	return 0;//完美撒花
}

STEP 4 完结撒花！

如果还有什么不懂的地方欢迎 $\text{评论区/私信}$ 问我哦，我会第一时间回复哒！

如果都懂了的话，就点个赞纪念一下你的成长8QWQ!