### harshalpamecha3's blog

By harshalpamecha3, history, 6 weeks ago,

• -6

 » 6 weeks ago, # |   0 Your mod calculation is wrong, you cannot simply divide by 2 in the end.
•  » » 6 weeks ago, # ^ |   0 Thanks
 » 6 weeks ago, # |   +1 You cannot divide 2 directly because it is modulo value of answer. So you should take inverse of 2 and then simply multiply with the answer in the end. Top Down Dp#include using namespace std; const int mod = 1000000007; long long int dp[501][125251];// Maximum States long long go(int n, long long int taken, long long int total) { if(n == 0) // Base Condition { if(taken == total) return 1; else return 0; } if(dp[n][taken] != -1) return dp[n][taken]; long long int include = go(n-1, taken+n, total-n); // Include n long long int exclude = go(n-1, taken, total); // Exclude n long long ans = (include + exclude) % mod; return dp[n][taken] = ans; } long long int power(long long base, long long exp, int mod) { long long int res = 1; while(exp) { if(exp&1) { res = (res*base)%mod; } exp /=2; base = (base*base)%mod; } return res; } int main() { int n; cin >> n; long long total = n*(n + 1)/2; // Sum of 1st n numbers long long taken = 0; memset(dp, -1, sizeof(dp)); long long inverseOf2 = power(2, mod-2, mod) % mod; // Modulo Inverse of 2 cout << (go(n, taken, total)*inverseOf2)%mod << '\n'; return 0; } 
•  » » 6 weeks ago, # ^ |   0 thanks
•  » » 6 weeks ago, # ^ |   0 As an alternative you can do the whole dp calculations with %(2*mod)This works because the factor 2 is fairly small, and 2*mod is still within the bounds of an integer. Then the division by 2 in the end yields the correct result.
•  » » » 6 weeks ago, # ^ |   0 Why 2*mod? Would you please tell me the logic behind this?
•  » » » 6 weeks ago, # ^ |   +1 No offense, but this approach seems very risky. I think "properly" multiplying with modinverse(2) should be the only approach suggested.