### harshalpamecha3's blog

By harshalpamecha3, history, 4 months ago,  Comments (7)
 » 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;// 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; } 
•  » » » No offense, but this approach seems very risky. I think "properly" multiplying with modinverse(2) should be the only approach suggested.