Untitled
unknown
plain_text
a year ago
1.8 kB
16
Indexable
public class Solution { HashMap<Long, Long> hm = new HashMap<>(); int mod = (int)(1e9+7); public long fastPow(int a, long n){ if(n == 0){ return 1; } long res = fastPow(a, n/2) % mod; if(n % 2 == 0){ return (res*res) % mod; } else{ return (((res * res) % mod) * a) % mod; } } private long nCr(long n, long r) { if (r > n) { return 0; } if (r == 0 || n == r) { return 1; } if (hm.containsKey(n * mod + r)) { return hm.get(n * mod + r); } long result = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % mod; hm.put(n * mod + r, result); return result; } public long findWays(long n){ if(n == 0){ return 0; } if(n == 1 || n == 2){ return 1; } if(hm.containsKey(n)){ return hm.get(n); } //h is the second last level of the tree as the elements are completely filled till 2nd last level //the above is the property of complete binary tree long h = (long)(Math.log(n) / Math.log(2)); long x = ((long)fastPow(2, h) - 1) % mod; long leftCount = ((long)x-1)/2; leftCount = (leftCount + Math.min(n - x, ((long)x+1)/2)) % mod; long rightCount = ((long)n - 1 - leftCount) % mod; long ways = (nCr(n-1, leftCount)) % mod; hm.put(n, (long)((((ways * findWays(leftCount)) % mod) * findWays(rightCount)) % mod)); return hm.get(n); } public int solve(int A) { return (int)(findWays(A) % mod); } }
Editor is loading...
Leave a Comment