| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19321 |
2016-02-24T09:42:15 Z |
xdoju |
Ω (kriii4_P3) |
C++14 |
|
0 ms |
1128 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];
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 21 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 22 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 23 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 24 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 25 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 26 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 27 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 28 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 29 |
Correct |
0 ms |
1128 KB |
Output is correct |
| 30 |
Correct |
0 ms |
1128 KB |
Output is correct |
