Submission #19317

#	Time	Username	Problem	Language	Result	Execution time	Memory
19317		xdoju	Ω (kriii4_P3)	C++14	0 / 100	0 ms	1124 KiB

P3

#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 / 100