Submission #19321

#	Time	Username	Problem	Language	Result	Execution time	Memory
19321		xdoju	Ω (kriii4_P3)	C++14	100 / 100	0 ms	1128 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];
long long coff[200];

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

	long long g;

	coff[1] = ((p - q) * modinv(p)) % MOD;

	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) {
		long long t = ((p - q) * modinv(p)) % MOD;

		long long u = (((coff[i - 1] * q) % MOD) * modinv(p)) % MOD;
		long long v = (1 - u + MOD) % MOD;

		coff[i] = (t * modinv(v)) % MOD;
	}

	long long res = 1;
	for (int i = n - 1; i >= k; --i) {
		res = (res * coff[i]) % MOD;
	}
	printf("%lld", res);
}

int main() {
	//freopen("input.txt", "r", stdin);
	proc();
	return 0;
}

• Subtask 1: 100 / 100