AIsing Programming Contest 2020 Question D Solution

Hits: 0

Topic link : https://atcoder.jp/contests/aising2020/tasks/aising2020_d

The main idea of ​​the title : give a 01 string of length n, reverse the i position (0 to 1, 1 to 0);
f(x): the number of 1s when x is converted to binary y,x=x% y, the number of times to loop when x==0.
Solve for i (0~n-1), convert the 01 string after inversion of i into decimal x, and find the value of f(x).

Idea : The total length of the 01 string is 2e5, so it can be imagined that after taking %mod once, the value must be within the range of 2e5. Then you can get violent results. The question is how to get the first mod? First of all, we preprocess the number of 1 to one, and step by step from the high bit 2 + the value of this bit %mod. Obviously, each processing case is one+1 or one-1, so mod is equal to one-1 or one+1. Because the calculation needs to be repeated, the whole is calculated first, and then only -2 i or +2 i is needed .
Points to note* : 1. There is a big hole in the calculation process, that is, the number of 1s will become 0. This requires special judgment.
2. The fast power needs to open long long.

Then we can happily ac. (see code for details)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;

ll qpow(ll x,ll n,int mod)
{
    ll sum=1;
    while(n){
        if(n&1) sum=sum*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return sum;
}
int ans(int x)
{
    if(x==0) return 0;
    int kk=__builtin_popcount(x);
    return 1+ans(x%kk);
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    string s;cin>>s;
    int one=0;
    for(int i=0;i<n;i++){
        if(s[i]=='1') one++;
    }
    int p1=0,p2=0;
    for(int i=0;i<n;i++){
        if(one!=1){
            p1=(p1*2+s[i]-'0')%(one-1);
        }
        p2=(p2*2+s[i]-'0')%(one+1);
    }
    for(int i=0;i<n;i++){
        if((s[i]=='1'&&one==1)){
            cout<<0<<endl;
        }
        else if(s[i]=='1'){
            cout<<1+ans((p1-qpow(2,n-i-1,one-1)+(one-1))%(one-1))<<endl;
        }
        else if(s[i]=='0'){
            cout<<1+ans((p2+qpow(2,n-i-1,one+1)+(one+1))%(one+1))<<endl;
        }
    }
    return 0;
}

Welcome to point out.

You may also like...

Leave a Reply

Your email address will not be published.