文档章节

UR#6 懒癌

o
 osc_n6euf5h6
发布于 2019/03/19 18:37
字数 813
阅读 10
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

超级结论题。。。

首先建出原图的补图,再考虑缩点。

缩完点后是一个有向无环图。 这个图的每个点代表一个强联通分量。 考虑一个大小大于$1$的强联通分量中的一个点$i$,那么$i$永远不可能开枪。

因为$i$开枪需要假设自己的狗没病,然后枚举自己看不到的狗的状态,然而由于有他的转移依赖的状态 依赖他,那么就会循环转移。 导致他一直到inf都不会开枪。

那么任何可以到达大于1的强联通分量的强联通分量都废了(包括本身),因为他们中所有点都只能不是病狗。

现在每个强联通分量都是单点强联通分量。

考虑一个状态,每个病狗的主人都非常聪明但也非常谨慎,它从他的狗没病,并且他不知道的狗状态随便的状态 中 开枪时间最大 的一种 转移过来。 然后所有主人的答案取$min$。 这样一次最多在 可到达点集 中去掉一个点,且肯定可以去掉一个点,因为拓扑序最小的点肯定去掉后再也不能被染黑了。 那么可以容易得出,状态的贡献就是它可以到的点集大小。再计算点的贡献。

考虑只有凸集上的点才能贡献答案(因为你取min的时候只能选凸集上的点),第二问也可以用点的贡献做。

#include <bits/stdc++.h>


using namespace std;
const int N=3010;
typedef long long ll;
int dfn[N],low[N],clk;
int isc[N],sz[N],nscc;
stack<int> st;
vector<int> e[N],g[N];
void Tajan(int x){
	//cerr<<"Tajan"<<x<<endl;
	dfn[x]=low[x]=++clk;
	st.push(x);
	for (auto i:e[x]){
		if (!dfn[i]) Tajan(i);
		if (!isc[i]) low[x]=min(low[x],low[i]);
	}
	if (dfn[x]==low[x]){
		++nscc;
		while (1){
			int u=st.top(); st.pop();
			isc[u]=nscc;
			++sz[nscc];
			//cerr<<"pop"<<nscc<<" "<<u<<endl;
			if (u==x) break;
		}
	}
}
bitset<N> b[N];

const int M=998244353;

int add(int x,int y){
	return (x+=y)>=M?x-M:x;
}
int sub(int x,int y){
	return (x-=y)<0?x+M:x;
}
int fp(int x,int y){
	int ret=1;
	for (; y; y>>=1,x=(ll)x*x%M) if (y&1) ret=(ll)ret*x%M;
	return ret;
}
char s[N];
int n;
int fc[N];
vector<int> ups[N];
int f[N];
int main(){
	scanf("%d",&n);
	for (int i=1; i<=n; ++i){
		scanf("%s",s+1);
		for (int j=1; j<=n; ++j)
			if (j!=i&&s[j]=='0'){
				//cerr<<i<<" "<<j<<endl;
				e[i].push_back(j);
			}
	}

	for (int i=1; i<=n; ++i){
		//cerr<<"????"<<i<<endl;
		if (!dfn[i]) Tajan(i);
	}
	//cerr<<nscc<<endl;
	for (int i=1; i<=n; ++i){
		for (auto j:e[i]){
			int x=isc[i];
			int y=isc[j];
			ups[y].push_back(x);
			if (sz[x]>1||sz[y]>1) continue;
			g[x].push_back(y);
		}
	}
	queue<int> q;
	for (int i=1; i<=nscc; ++i)
		if (sz[i]>1) q.push(i),f[i]=0; else f[i]=1000000;
	while (!q.empty()){
		int x=q.front(); q.pop();
		for (auto j:ups[x])
			if (f[j]==1000000){
				f[j]=f[x]+1;
				q.push(j);
			}
	}
	int tot=0,ans1=0,ans2=0;
	for (int i=1; i<=nscc; ++i) tot+=(sz[i]==1&&f[i]==1000000);
	for (int i=1; i<=n; ++i) fc[isc[i]]=i;
	for (int i=nscc; i>=1; --i)
		if (sz[i]==1&&f[i]==1000000){
			//cerr<<fc[i]<<endl;
			//cerr<<i<<" "<<fc[i]<<endl;
			b[i].set(fc[i]);
			for (auto j:g[i]) b[j]|=b[i];
			ans1=add(ans1,(ll)sub(fp(2,b[i].count()),1)*fp(2,tot-b[i].count())%M);
			ans2=add(ans2,fp(2,tot-b[i].count()));
		}
	cout<<ans1<<" "<<ans2<<endl;
}
下一篇: Maven
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
“懒癌”患者必备的PDF转Word工具

每个月你是不是总有那么二十九天不想上班;上班时懒得思考问题,太费脑筋;放假时就懒得下楼,懒得逛街。能坐着绝不站着,能躺着绝不坐着;手伸不到的地方,都是到不了的远方;聊天能发表情,...

米苏啦啦噜
2018/08/24
2
0
Android TabLayout 库--FlycoTabLayout

FlycoTabLayout 是一个 Android TabLayout 库,目前有两个 TabLayout。 SlidingTabLayout:参照 PagerSlidingTabStrip 进行大量修改。 新增部分属性 新增支持多种 Indicator 显示器 新增支持...

孔小菜
2015/11/11
6.3K
1
MySQl安装教程详解(一)

MySql mysql下载 官网链接:https://dev.mysql.com/downloads/ 懒癌直下:https://dev.mysql.com/get/Downloads/MySQLInstaller/mysql-installer-community-8.0.16.0.msihttps://dev.mysql.......

随遇而安870890
03/11
1
0
最新动漫绘画自学教程:动漫绘画自学学的方法!

最新动漫绘画自学教程:动漫绘画自学学的方法!目前学习插画的方式,不外乎书籍、教程、公开课、培训班等四种方式,首先书籍的话,可以去豆瓣看一下哪些评分较高以及一些学生的评价。 如果是...

动漫绘画学习教程
2019/04/28
0
0
灵猫课堂靠谱吗?学生用作品说话!

灵猫课堂靠谱吗?绘画是一个累积的过程,对于基础比较差的同学而言,首先第一步是学会坚持,其次就是把基础打牢固,现在培训班多如牛毛,很多机构为了达到节省成本与宣传目的,大力包装学生,...

动漫绘画学习教程
2019/05/10
1
0

没有更多内容

加载失败,请刷新页面

加载更多

Python骚操作 | 川普的嘴,骗人的鬼!

↑ 关注 + 星标 ,后台回复【 大礼包 】送你Python自学大礼包 阅读文本大概需要 3 分钟 前几天,川普又在推特因为宣扬暴力翻车了,不过,对于这位翻车王来说,已经是常规操作了。在推特上指点...

Python绿色通道
06/19
0
0
(五)改掉这些坏习惯,还怕写不出精简的代码?

鲁迅说:嬉笑怒骂里充满了无奈和妥协。 小猿说:先生说的不对,在程序员的世界里,编写代码处处充满了无奈和妥协。 Code Review 是一场苦涩但有意思的修行。 (一)改掉这些坏习惯,还怕写不...

一猿小讲
06/15
4
0
Linus:我们都老了,但Linux维护后继无人

点击上方“五分钟学算法”,选择“星标”公众号 重磅干货,第一时间送达 来自:大数据文摘(ID:BigDataDigest)出品 来源:theregister 编译:笪洁 本周在线举行的开源峰会和嵌入式Linux会议...

五分钟学算法
07/08
5
0
腾讯应用宝:首次上传演示视频需要去腾讯视频进行实名认证的操作

前段时间打算把刚开发好的Android应用上架到腾讯的应用宝商店,但是由于业务的需要,需要上传App的操作演示视频,由于是首次在应用宝上面上架App,需要处理的东西太多,这里就不再一一介绍,...

sanzhanggui
2019/12/14
0
0
祝大家端午节快乐!

端午节快乐 本文分享自微信公众号 - 嘉为科技(canway_service)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

嘉为科技
06/24
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部