I am counting for odd count only, in line 119 I am incrementing i+=2 ,
i guess this is what u mean, Or may be i have understood it in wrong way
Can anyone who have just solved subtask 1 share their code link? Thanks in advance
First things first what is a convolution ??
And how did you reach to the conclusion that it requires convolution ?
Read the FFT/NTT link I have mentioned.
Can you share some resources to learn the underlying concepts?
In your code ,you are looping from i=1 to i<=j and calculating ncr for xCi but eventually i will exceed x for some cases in which your value should be 0 (eg:-3C5 should be 0)but your code is not doing that.
https://www.codechef.com/viewsolution/42849133
This is your code with only if(R>N) return 0; this line added in your Binomial function. Subtask 1 AC and rest tle.
1 Like
thanks , should have seen that while contest 
Convolution is basically a mathematical operation on 2 functions which leads to a resultant function. Generally, if we represent a function a set a values[array], the value of the resultant function at each index is series summation of product of elements from both input functions in a particular way as shown below. Here in the context of this problem as well, for finding the solution for a particular value of M, we see a summation series which is identical to polynomial multiplication.
Exploring polynomial multiplication, could recollect that it is a convolution as I studied it during college days. FFT/NTT used to solve convolution with same approach in different fields in nlogn time complexity.
FFT-less solution cuz im a noob: CodeChef: Practical coding for everyone
For size i, I xor’d each element to the subsequences of size i-1. This would give me subsequences of size i-2 and i, which i subtracted and divided respectively to get the actual answer for size i.
2 Likes
Hi all,
I have tried to solve the problem in python. I kept getting TLE. I have applied recommendations like optimizations by use functions, avoided nested for loops and have also used inbuilt libraries which are efficient in working
Solution link https://www.codechef.com/viewsolution/42725945
Any replies which can help me to further understand why I got TLE will certainly help a lot.
There is no doubt you will get TLE for even much smaller values of N beyond 20-25.
If you are going to enlist all subsets of a set of size N, you will get complexity 2^N.
In this problem, even N^2 struggles to pass all test cases and NlogN is required.
1 Like
yeah, Sorry , I missed that iteration was i+=2,
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
https://www.codechef.com/viewsolution/42934327
Why I am getting TLE?. What should I optimize?
Can anyone help me.
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
Thanks!
I thought my fft implementation was the problem.
Though the problem have tough constraint.
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;
}
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 
2 Likes