P7681 题解

· · 题解

题目描述（摘自原题）

一个班有 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';
    }
}