AIsing Programming Contest 2020 D - Anything Goes to Zero

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define ull unsigned long long
 5 #define pb push_back
 6 const int maxn=2e5+10;
 7 const int mod=1e9+7;
 8 char s[maxn];
 9 vector<int>ans;
10 int f(int x)
11 {
12     int cnt=0;
13     while(x)
14     {
15         x%=__builtin_popcount(x);
16         cnt++;
17     }
18     return cnt+1;
19 }
20 ll power(ll base,ll n,ll m)
21 {
22     ll r=1;
23     while(n)
24     {
25         if(n&1) r=r*base%m;
26         base=base*base%m;
27         n/=2;
28     }
29     return r;
30 }
31 
32 int main()
33 {
34     ios::sync_with_stdio(false);
35     cin.tie(0);
36     int n;
37     cin>>n;
38     cin>>(s+1);
39     int sum=0;
40     for(int i=1;i<=n;i++)
41     {
42         if(s[i]==‘1‘)
43             sum++;
44     }
45     ll sum1=0;
46     ll sum0=0;
47     reverse(s+1,s+1+n);
48     for(int i=1;i<=n;i++)
49     {
50         if(s[i]==‘1‘)
51         {
52             sum0+=power(2,i-1,sum+1);
53             sum0%=(sum+1);
54             if(sum-1==0)
55                 continue;
56             sum1+=power(2,i-1,sum-1);
57             sum1%=(sum-1);
58 
59         }
60     }
61     for(int i=1;i<=n;i++)
62     {
63         if(s[i]==‘1‘)
64         {
65             if(sum-1==0)
66             {
67                 ans.pb(0);
68                 continue;
69             }
70             ll temp=sum1-power(2,i-1,sum-1);
71             temp=(temp+sum-1)%(sum-1);
72             ans.pb(f(temp));
73         }
74         else
75         {
76             ll temp=sum0+power(2,i-1,sum+1);
77             temp%=sum+1;
78             ans.pb(f(temp));
79         }
80     }
81     reverse(ans.begin(),ans.end());
82     for(auto &v:ans)
83         cout<<v<<‘\n‘;
84 
85 
86 
87 
88 
89 
90 
91 
92 
93 }