oj.uz

답안 #19317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19317 2016-02-24T09:36:11 Z xdoju Ω (kriii4_P3) C++14
0 / 100
 0 ms 1124 KB 
#include <cstdio>
using namespace std;

const long long MOD = 1000000007ll;
int m;
int face[10000];

long modpow(long long r, long long n) {
	long long ret = 1;
	while (n > 0) {
		if (n % 2 > 0) {
			ret = (ret * r) % MOD;
		}
		r = (r * r) % MOD;
		n /= 2;
	}
	return ret;
}

long long modinv(int n) {
	return modpow(n, MOD - 2);
}

long long gcd(int a, int b) {
	if (a < b) {
		return gcd(b, a);
	}
	return (b == 0) ? a : gcd(b, a % b);
}

long long num[200], denom[200];

void proc() {
	int p, q, n, k;
	scanf("%d %d %d %d", &p, &q, &n, &k);
	if (k == n) {
		printf("1");
		return;
	}

	long long g;

	num[1] = p - q;  denom[1] = p;
	g = gcd(num[1], denom[1]);
	num[1] /= g;  denom[1] /= g;

	for (int i = 2; i < n; ++i) {
		num[i] = denom[i - 1] * (p - q);
		denom[i] = p * denom[i - 1] - q * num[i - 1];
		g = gcd(num[i], denom[i]);
		num[i] /= g;
		denom[i] /= g;
	}

	long long resnum = 1, resdenom = 1;
	for (int i = n - 1; i >= k; --i) {
		resnum *= num[i];
		resdenom *= denom[i];
		g = gcd(resnum, resdenom);
		resnum /= g;
		resdenom /= g;
	}
	printf("%lld", (resnum * modinv(resdenom)) % MOD);
}

int main() {
	proc();
	return 0;
}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1124 KB Output is correct
2 Runtime error 0 ms 1120 KB SIGFPE Floating point exception
3 Halted 0 ms 0 KB -