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
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
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