Acwing winter vacation daily question 2022 punch in day 11

Original link ：

1960. flashing - AcWing Question bank High quality algorithm question bank https://www.acwing.com/problem/content/1962/

Ideas ：

State compression + Looking for a ring , Keep enumerating the next state , Then save the number of steps in each state , If there is a repetition, it means there is a ring , Be sure to add the number of steps from the starting point to the ring , This question is mainly about training state compression , See code for details

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e7+10;
int p[N];
long long n,k;
int get(int now)
{
    int res=0;
    for(int i=0;i<n;i++)// Simulate the change operation according to the meaning of the topic 
    {
        int j=i-1;
        if(j==-1) j=n-1;
        int x=now>>i&1,y=now>>j&1;
        res|=(x^y)<<i;
    }
    return  res;
}
void print(int x)
{
    for(int i=0;i<n;i++)
    cout<<(x>>i&1)<<endl;
}
int main()
{
    cin>>n>>k;
    int star=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        star|=x<<i;
    }
    memset(p,-1,sizeof p);
    p[star]=0;
    int now=star;
    int t=0;
    for(int i=1;;i++)
    {
        now=get(now);

        if(i==k)
        {
            print(now);
            break;
        }


        if(p[now]!=-1)
        {
            t=i-p[now];
            for(int j=0;j<(k-i)%t;j++) now=get(now);// The number of steps left 
            print(now);
            break;
        }
        else
        p[now]=i;


    }
    return 0;
}

author ： Mechanical endurance
link ：https://www.acwing.com/activity/content/code/content/2421483/
source ：AcWing
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .