Subarray XOR Codechef Solution | MARCH LONG CHALLENGE

Codechef
Share:

Subarray XOR CodeChef Solution:

Mary loves binary strings.
Given a binary string SS, she defines the beauty of the string as the bitwise XOR of decimal representations of all substrings of SS.

Find the beauty of string SS. Since the answer can be huge, print it modulo 998244353998244353.

For example, the decimal representation of binary string 11011101 is 1β‹…23+1β‹…22+0β‹…21+1β‹…20=8+4+0+1=131β‹…23+1β‹…22+0β‹…21+1β‹…20=8+4+0+1=13. Kindly refer sample explanation for more such examples.

A string AA is a substring of a string BB if AA can be obtained from BB by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of test cases follow.
  • First line of each test case contains one integer NN – the length of the binary string.
  • Second line of each test case contains the binary string SS.

Output Format

For each test case, output in a single line, beauty of the string modulo 998244353998244353.

Constraints

  • 1≀T≀1001≀T≀100
  • 1≀N≀1051≀N≀105
  • Sum of NN over all test cases does not exceed 2β‹…1052β‹…105

Sample Input 1 

3
2
10
3
101
4
1111

Sample Output 1 

3
6
12

Explanation

Test Case 11: All substrings of the string S=10S=10 are [1,0,10][1,0,10]. The decimal representation of these substrings is denoted by the array [1,0,2][1,0,2]. Bitwise XOR of all these values is 1βŠ•0βŠ•2=31βŠ•0βŠ•2=3.

Test Case 22: All substrings of the string S=101S=101 are [1,0,1,10,01,101][1,0,1,10,01,101]. The decimal representation of these substrings is denoted by the array [1,0,1,2,1,5][1,0,1,2,1,5]. Bitwise XOR of all these values is: 1βŠ•0βŠ•1βŠ•2βŠ•1βŠ•5=61βŠ•0βŠ•1βŠ•2βŠ•1βŠ•5=6.

Test Case 33: All substrings of the string S=1111S=1111 are [1,1,1,1,11,11,11,111,111,1111][1,1,1,1,11,11,11,111,111,1111]. The decimal representation of these substrings is denoted by the array [1,1,1,1,3,3,3,7,7,15][1,1,1,1,3,3,3,7,7,15]. Bitwise XOR of all these values is: 1βŠ•1βŠ•1βŠ•1βŠ•3βŠ•3βŠ•3βŠ•7βŠ•7βŠ•15=121βŠ•1βŠ•1βŠ•1βŠ•3βŠ•3βŠ•3βŠ•7βŠ•7βŠ•15=12.

Subarray XOR Codechef SOLUTION

C++


#include <iostream> 
using namespace std; 
#define ll long long 
#define fun() int t; cin>>t; while(t--)
ll mod=998244353;
int main() {
    fun()
    {
        ll n; 
        cin>>n;
        string s; 
        cin>>s;
        ll a[n]={0}; 
        ll c=1; 
        ll solution=0;
        if(s [0] =='1')
        {
            a[0]=1;
        }
        ll arr=a[0]; 
        for(ll i=1;i<n; i++)
        {
            if(s[i]=='1')
            {
                arr+=(i+1);
            }
            a[i]=arr; 
            a[i]=a[i]%2;
        }
        for(ll i=n-1; i >=0; i--)
        {
            if(a[i]==1)
            {
                solution+=c; 
                solution=solution%mod;
            }
            c=c*2;
            c=c%mod;
        }
        cout<<solution%mod<<endl;
    }
    return 0;
}

Java


import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	    Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i=0;i<t;i++)
		{
		    int n = sc.nextInt();   
		    sc.nextLine();
		    String s = sc.nextLine();
            
            long mod = 998244353;
		    long[] arr = new long[n];
		    long res = 1;
		    long sol = 0;
		    
		    if(s.charAt(0)=='1')
		    {
		        arr[0] = 1;
		    }
		    
		    long temp = arr[0];
		    for(int j=1 ; j<n ; j++)
		    {
		        if(s.charAt(j) == '1')
		        {
		             temp +=(j+1);
		        }
		        arr[j] = temp;
		        arr[j] = arr[j]%2;
		        
		    }
		    for(int j=n-1;j>=0;j--)
		    {
		        if(arr[j]==1)
		        {
		            sol += res;
		            sol = sol%mod;
		        }
		        res = res*2;
		        res = res%mod;
		    }
		    System.out.println(sol%mod);
		}   
	}
}

Python



t = int(input())
for i in range (0, t):
        n = int(input())
        s = input()[:n]
        l1 = [0] * n
        p1 = 1
        if (s[0] == "1"):
                l1[0] = 1
        x = l1[0]
        ans = 0
        for j in range (1, n):
                if (s[j] == "1") :
                        x += j+1
                l1[j] = x
                l1[j] = l1[j]%2
        for j in range (n-1, -1, -1):        
                if (l1[j] == 1) :
                        ans += p1
                        ans %= 998244353
                p1 *= 2
        p1 %= 998244353
        print(ans%998244353)

Subarray XOR Codechef Solution Tutorial

Read More Post Here

Leave a Comment

Your email address will not be published. Required fields are marked *

x