oj.uz

Submission #20119

# Submission time Handle Problem Language Result Execution time Memory
20119 2016-02-26T05:42:27 Z sui Ω (kriii4_P3) C++14
0 / 100
 0 ms 1720 KB 
#define _CRT_SECURE_NO_WARNINGS // scanf(), gets() (needed for Visual C++)

//#define NDEBUG
#include <cassert>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>

#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <deque>

using namespace std;

#define MEMSET(x, WITH) memset(x, (WITH), sizeof(x))
#define FOR(i, E) for(int i=0; i<(E); i++)
#define REP(i, LO, HI) for(int i=(LO); i<=(HI); i++)

#define GETINT(x) scanf("%d", &x)
#define GETDBL(x) scanf("%lf", &x)
#define GETSTR(x) scanf("%s", x)
#define NEWINT(x) int x; scanf("%d", &x)
#define NEWDBL(x) double x; scanf("%lf", &x)
#define NEWLN putchar('\n')

#ifdef _WIN32
#define popcnt __popcnt
#else
#define popcnt __builtin_popcount
#endif

typedef long long ll;
//const ll MOD = 1000000007;
//const double PI = atan(1) * 4;







const ll MOD = 1000000007;

ll powerMod(ll a, ll n) {
	ll ans = 1;
	for (int i=62; i>=0; i--) {
		ans = ans * ans % MOD;
		if ((n>>i)&1)
			ans = ans * a % MOD;
	}
	return ans;
}
ll inv(ll a) {
	return powerMod(a, MOD-2);
}



// The probability to go down: Q/P
// The probability to go up: 1 - Q/P

ll P, Q, N, K;
// 0 <= Q <= P

int main() {
	cin >> P >> Q >> N >> K;

	if (Q == P) puts("0");
	else if (Q == 0) puts("1");
	else if (K == 0) puts("0");
	else if (K == N) puts("1");
	else {

		ll r = Q * inv(P-Q) % MOD;
		if (r == 1) {
			cout << K * inv(N) % MOD << endl; return 0;
		}




		ll numer = (powerMod(r, K)-1+MOD) % MOD;
		ll denom = (powerMod(r, N)-1+MOD) % MOD;
		ll ans = numer * inv(denom) % MOD;

		cout << ans << endl;

	}






	return 0;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1720 KB Output is correct
2 Correct 0 ms 1720 KB Output is correct
3 Incorrect 0 ms 1720 KB Output isn't correct
4 Halted 0 ms 0 KB -