SUMXOR2 - Editorial

editorial
, , , ,
47

I have implemented her algo post contest while improving on time & memory. I have also documented my understanding in the code itself. Do check if you are still looking for explanation of DP solution for this problem.
https://www.codechef.com/viewsolution/42862006

2 Likes
48

https://www.codechef.com/viewsolution/42934327

Why I am getting TLE?. What should I optimize?
Can anyone help me.

49

here is your modified code, basically ncr function was bottlenecking , also i had modified few more lines .
https://www.codechef.com/viewsolution/42971420

1 Like
50

Thanks!
I thought my fft implementation was the problem.
Though the problem have tough constraint.

51

Can someone help me for 1st subtask?
I am gettting WA for 1st subtask and i don’t know why. I have implemented it as given in editorial and used modulo operations wherever necessary.
If anyone can help me it would be great help. Thanks.

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353ll
#define endl "\n"
#define mxn 100002ll
long long f[mxn];
void init(){
	f[0] = 1LL;
	for(long long i=1LL;i<=mxn;i++){
		f[i] = ((f[i-1LL]*i)%mod + mod)%mod;
	}
}

long long ncr(long long n, long long r){
	if(n<0 || r<0 || n<r) return 0;
	long long a = f[n];
	long long b = f[r];
	long long c = f[n-r];
	long long div = b*c;
	div = (div%mod + mod)%mod;
	long long ret = a/(div);
	ret = (ret%mod + mod)%mod;
	return ret;
}

int main(){
	init();

	long long n;
	cin >> n;
	long long a[n];
	for(long long i=0;i<n;i++){
		cin >> a[i];
	}
	if(n>10000) return 0;

	long long n1[32ll];
	memset(n1,0,sizeof(n1));
	for(long long i=0;i<32LL;i++){
		for(long long j=0;j<n;j++){
			if((1LL<<i)&a[j]) n1[i]++;
		}
	}

	long long n0[32ll];
	for(long long i=0;i<32ll;i++){
		n0[i] = n - n1[i];
	}

	// for(int i=0;i<10;i++){
	// 	cout << n1[i] << " ";
	// }cout << endl;

	long long ans[mxn];
	ans[0] = 0;

	for(long long m=1ll;m<=n;m++){

		long long cont = 0;
		for(long long bit=0;bit<32LL;bit++){
			long long s = 0;
			//choose 1,3,5,..,n1[bit]
			for(long long j=1ll;j<=n1[bit];j+=2ll){
				long long a = ncr(n1[bit],j); a = (a%mod + mod)%mod;
				long long b = ncr(n0[bit],m-j); b = (b%mod + mod)%mod;
				s += ((a*b)%mod + mod)%mod;
				s = (s%mod + mod)%mod;
			}
			s = (((1LL<<bit)*s)%mod + mod)%mod;
			// cout << "s="<<s<<endl;
			cont += s;
			cont = (cont%mod + mod)%mod;
		}

		ans[m] = (ans[m-1] + cont)%mod;
		ans[m] = (ans[m]%mod + mod)%mod;
	}

	int q;
	cin >> q;
	while(q--){
		int m;
		cin >> m;
		cout << ans[m]<< endl;
	}

	return 0;
}
52

The problem is in your ncr function. The distributive property of mod does not apply to division.(a/b)%m is not ((a%m)/(b%m) )%m.Here are some links to help you with that-

I modified your ncr function a bit and added a binary exponentiation function and got subtask 1 AC-CodeChef: Practical coding for everyone
Hope this helps :v:

2 Likes