自动搬运

查看原文

来自洛谷，原作者为

	YangHHao 你好,OI

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

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

以下是正文

题目描述（摘自原题）

一个班有 $n$ 个孩子，他们上课时并没有认真听课，而是在玩 Facebook 社交网页上的扔西瓜游戏。

第一节课上，Goran 向他的每个朋友扔了一个西瓜，随后几节课，孩子们都会按照以下方式采取行动：

如果上节课一个人被奇数个西瓜扔中，那么这节课他会向所有他的朋友各扔一个西瓜。 如果上节课一个人被偶数（包括 $0$）个西瓜扔中，那么这节课他会向所有他的朋友各扔两个西瓜。 孩子们按照 $1\sim n$ 编号，其中 Goran 的编号为 $1$。

现在，给定孩子的个数 $1$ 和他们所有人的朋友关系，请求出 $1$ 节课之后，孩子们一共扔了多少个西瓜。

数据范围

对于所有数据，$1\leqslant n\leqslant 20$，$1\leqslant h\leqslant 10^9$。

思路

观察到： $n$ 的范围很小，同时一节课上每个人的贡献（丢出的西瓜数）只和其上节课被扔的西瓜数有关。

考虑使用 bitset，这样每个人每节课只需要一次与操作即可，成功将时间复杂度从 $O(T\cdot n^2)$ 降为 $O(T \cdot n)$。

但是不管再怎么削减计算复杂度，$h$ 的 $10^9$ 数量级还是太大了。怎么办呢？

一张丑丑的图

观察到，在一定节课以后，必定会出现一段循环。图中就体现为第三节课以后都受偶数西瓜。这是因为每次的情况只与上一次有关，且情况最多只有 $2^n$ 种。

再回头看 $n$ 的范围，应该就能知道 $h$ 的处理方法：

计算出第一次循环的开始和结束，给 $h$ 掐掉头以后做除法即可

时间复杂度 $O(n \cdot 2^n)$，实现起来很快，你谷上 AC 记录的总时间此题解发表时都在 100 ms 以内

下面是代码，如果具体实现有问题可以看注释。

#include<bits/stdc++.h>
using namespace std;
#define int long long  //麻麻再也不用担心我忘记开long long了！ 
#define rep(i,s,t) for(int i=(s);i<=(t);++i)
#define irep(i,t,s) for(int i=(t);i>=(s);--i)
const int N=21;
int n,h,val[1<<N],cnt[N];     //val数组记录每回合答案（的前缀和），cnt数组记录朋友数（用以计算贡献） 
bitset<20> gt[1<<N],fnd[N];   //gt（get）数组记录一节课上每个人被丢西瓜的奇偶，fnd（friend）记录一个人的朋友 
map<int,int>used;  // used数组记录一种排列上次出现的位置 
signed main(){
	cin>>n>>h;
	rep(i,0,n-1){
		rep(j,0,n-1){
			char c=getchar();
			while(c<'0'||c>'1')c=getchar();
			fnd[i][j]=c-'0';
		}
		cnt[i]=fnd[i].count();
	}
	val[0]=cnt[0];  //初始一节课的情况 
	gt[0]=1;
	int k=0;
	for(k=1;k<=(1<<n)+10;++k){
		rep(i,0,n-1){
			gt[k][i]=(fnd[i]&gt[k-1]).count()&1;
			val[k]+=cnt[i]*(2-gt[k][i]);
		}
		if(used.count(gt[k].to_ulong()))break;  
		used[gt[k].to_ulong()]=k;    //记录次情况出现的课节
		//to_ulong是将bitset转为整型的函数，方便放入map中排序，就不用打比较函数了 
	}
	int ans=0,st=used[gt[k].to_ulong()];
	rep(i,1,(1<<n)+10){
		val[i]+=val[i-1]; //计算前缀和 
	} 
	if(h<=st){  //如果没有进入循环
		cout<<val[h-1]<<'\n';
	}
	else{  //否则
		h-=st;
		ans+=val[st-1];
		ans+=h/(k-st)*(val[k-1]-val[st-1]);
		ans+=val[h%(k-st)+st-1]-val[st-1];
		cout<<ans<<'\n';
	}
}