Please Login in order to post a comment
C++ solution
#include <bits/stdc++.h> using namespace std; typedef long long int64; const int inf = (1 << 30) - 1; const int64 linf = (1ll << 62) - 1; const int N = 3e5 + 100; const int M = 1e9 + 7; int n, m, k; int fact[N], ifact[N]; inline int power(int a, int b){ int res = 1; for(; b; b >>= 1){ if(b & 1){ res = (1ll * res * a) % M; } a = (1ll * a * a) % M; } return res; } inline int inv(int x){ return power(x, M - 2); } inline void precalc(){ fact[0] = ifact[0] = 1; for(int i = 1; i < N; i++){ fact[i] = (1ll * fact[i - 1] * i) % M; ifact[i] = (1ll * ifact[i - 1] * inv(i)) % M; } } inline int cnk(int n, int k){ if(k < 0 || k > n){ return 0; } int cur1 = (1ll * fact[n] * ifact[k]) % M; return (1ll * cur1 * ifact[n - k]) % M; } int main(){ precalc(); cin >> n >> m >> k; k = k * 2 / m; int ans = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j * i <= n - 1; j++){ int cur1 = (1ll * power(m, n - j * i) * power(m - k, j)) % M; int cur2 = (1ll * cur1 * power(k, j * (i - 1))) % M; int cur3 = (1ll * cur2 * cnk(n - j * (i - 1) - 1, j)) % M; if(j & 1){ if((ans += cur3) >= M){ ans -= M; } } else{ if((ans -= cur3) < 0){ ans += M; } } } for(int j = 0; j * i <= n - i; j++){ int cur1 = (1ll * power(m, n - (j + 1) * i + 1) * power(m - k, j)) % M; int cur2 = (1ll * cur1 * power(k, (j + 1) * (i - 1))) % M; int cur3 = (1ll * cur2 * cnk(n - j * (i - 1) - i, j)) % M; if(j & 1){ if((ans -= cur3) < 0){ ans += M; } } else{ if((ans += cur3) >= M){ ans -= M; } } } } cout << (1ll * ans * inv(power(m, n))) % M << endl; return 0; }
Actually there's an O(n log n) solution - calculating in O(n/x) for each "x" mentioned in editorial :)
No more comments
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
C++ solution
Actually there's an O(n log n) solution - calculating in O(n/x) for each "x" mentioned in editorial :)