PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Nabil BOUDRA
Tester: Harris Leung
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
XOR
PROBLEM:
Given an integer N, find out the value of \sum\limits_{i=1}^{2^n-1} f(i) modulo 998244353 or claim that there exists a positive integer x <2N for which f is undefined.
EXPLANATION:
Let’s realize that f will never be undefined and the maximum value that f(x) can achieve is 3. Let’s see how:
1) Numbers whose binary representation are palindrome.
- It’s easy to observe that the numbers whose binary representations are palindromes. If we reverse these binary representations, we will be getting the same number. And as we know the xor property that X \oplus X = 0. Hence such numbers will take only a 1 operation.
2) Numbers whose binary representation ends at 0
- Let’s say the binary representation of such number is B_1, B_2, B_3,\dots,B_N. Now if we reverse this binary representation we will be getting B_N, B_N-1, B_N-2,\dots,B_1. Now let’s do the xor of these two binary representations:
- Observe that the 1st index and last index will be the same as at both the index we are doing B_1 \oplus B_N. Similarly, in all the indexes, it is followed. Hence after one operation, our X will be palindrome and hence such numbers will require 2 operations.
3) Numbers whose binary representation ends at 1
-
Aren’t these numbers also become palindromes after one operation. The answer is NO else why would it be a separate case. So Why?
-
Actually the first bit after performing xor becomes 0 and hence the binary representation is no more a palindrome but guess what your last bit becomes 0 after doing operation 1 time. Hence these types of numbers require 3 operations.
So, it’s quite clear that the maximum value f(x) can achieve is 3. Also, we know which type of numbers will have what value.
- Now the numbers whose binary representations are palindromes follows a series like
-
The numbers whose binary representations start and end with 1 are 2^{(n-1)}.
-
And the rest are the remaining numbers.
Now, you can easily find the answer as you know the value of f(x) for each type of this number.
ForIimplementation part, you can refer to the Editorialist Solution with comments.
TIME COMPLEXITY:
O(logN) per test case.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf = 1e9,md=998244353 ,mxn=6;
int be(int a , int b){
int ans=1;
while(b){
if(b&1)ans*=a;
b/=2;
a*=a;
ans%=md;
a%=md;
}
return ans ;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int q ;
cin>>q ;
while(q--){
int n ;
cin>>n ;
int ans=(be(2,n)+md-2)*4;
ans%=md;
ans+=3*(md-be(2,n-1)+1);
ans%=md;
int thing=0;
if(n%2==1&&n>1){
thing = 2*(be(2,(n-2)/2+1)+md-1)+be(2,(n-1)/2)+md-1;
}
else if(n%2==0)
thing = 2*(be(2,(n-1)/2+1)+md-1)+md-1;
thing%=md;
thing=md*2-thing*2;
thing%=md;
ans+=thing;
ans%=md;
ans++;
ans%=md;
cout<<ans<<endl;
}
return 0 ;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
ll pw(ll x,ll y){
if(y==0) return 1;
if(y%2) return x*pw(x,y-1)%mod;
ll res=pw(x,y/2);
return res*res%mod;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
ll n;cin >> n;
ll ans;
if(n%2==1){
ans=pw(2,n-1)*5-pw(2,(n-1)/2)*6+2;
ans=ans%mod+mod;
ans%=mod;
}
else{
ans=pw(2,n-1)*5-pw(2,n/2)*4+2;
ans=ans%mod+mod;
ans%=mod;
}
cout << ans << '\n';
}
}
Editorialsit's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int pw(int x,int y){
if(y==0) return 1;
if(y%2) return x*pw(x,y-1)%mod;
int res=pw(x,y/2);
return res*res%mod;
}
void solve()
{
int n;
cin>>n;
if(n==1)
cout<<1<<"\n";
else if(n%2 == 0)
{
/* Let's assume for now that all number requires 2 operations.
Hence our answer will be 2*(2^n-1), let's find that.*/
int ans = pw(2,n);
ans = ans-1;
while(ans<0)
ans+=mod;
ans = (ans*2)%mod;
/* Now all the numbers which begin with 1 and end at 1 are (2^(n-1)).
These numbers require one extra operation hence let's add (2^(n-1))
to our answer.*/
ans = (ans+pw(2,n-1))%mod;
/* Now let's calculate all palindrome's we saw in an editorial they form
a series like 1+1+2+2+4+4+.........
Let's join in pairs and we get 2+4+8+...
It's a GP with n/2 terms and hence you can easily find the sum.
Now all these numbers require a single operation hence subtract (2*sum)
from the answer*/
int temp = pw(2,n/2);
temp = temp-1;
while(temp<0)
temp+=mod;
temp = (temp*4)%mod;
ans-=temp;
while(ans<0)
ans+=mod;
// Ya we got our final answer.
cout<<ans<<"\n";
}
else
{
/* Let's assume for now that all number requires 2 operations.
Hence our answer will be 2*(2^n-1), let's find that.*/
int ans = pw(2,n);
ans = ans-1;
while(ans<0)
ans+=mod;
ans = (ans*2)%mod;
/* Now all the numbers which begin with 1 and end at 1 are (2^(n-1)).
These numbers require one extra operation hence let's add (2^(n-1))
to our answer.*/
ans = (ans+pw(2,n-1))%mod;
/* Now let's calculate all palindrome's we saw in an editorial they form
a series like 1+1+2+2+4+4+.........
Let's join in pairs and we get 2+4+8+...
It's a GP with n/2 terms and hence you can easily find the sum.
Remember as N is odd hence there will be one addition term i.e 2^(N/2),
just add this number too in the sum calculated from GP.
Now all these numbers require a single operation hence subtract (2*sum)
from the answer*/
int temp = pw(2,n/2);
temp = temp-1;
while(temp<0)
temp+=mod;
temp = (temp*2)%mod;
temp = (temp+pw(2,n/2))%mod;
temp = (temp*2)%mod;
ans-=temp;
while(ans<0)
ans+=mod;
// Ya we got our final answer.
cout<<ans<<"\n";
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}