답안 #19061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19061 2016-02-17T23:42:54 Z kriii Ω (kriii4_P3) C++14
100 / 100
0 ms 1084 KB
#include <stdio.h>
  
const long long mod = 1000000007;
  
long long fpow(long long a, long long p)
{
    a = (a % mod + mod) % mod;
    p = (p % (mod - 1) + mod - 1) % (mod - 1);
    long long r = 1;
    while (p){
        if (p & 1) r = r * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return r;
}
  
int main()
{ 
    int P,Q,N,K; scanf ("%d %d %d %d",&P,&Q,&N,&K);
  
    if (K == 0) puts("0");
    else if (K == N) puts("1");
    else if (Q == 0) puts("1");
    else if (Q == P) puts("0");
    else{
        long long v[101];
        long long pr = Q * fpow(P,-1) % mod, rv = fpow(1-pr,-1);
        v[0] = 0; v[1] = 1;
        for (int i=2;i<=N;i++) v[i] = ((v[i-1] - pr * v[i-2]) % mod * rv % mod + mod) % mod;
        printf ("%lld\n",v[K]*fpow(v[N],-1)%mod);
    }
  
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Correct 0 ms 1084 KB Output is correct
3 Correct 0 ms 1084 KB Output is correct
4 Correct 0 ms 1084 KB Output is correct
5 Correct 0 ms 1084 KB Output is correct
6 Correct 0 ms 1084 KB Output is correct
7 Correct 0 ms 1084 KB Output is correct
8 Correct 0 ms 1084 KB Output is correct
9 Correct 0 ms 1084 KB Output is correct
10 Correct 0 ms 1084 KB Output is correct
11 Correct 0 ms 1084 KB Output is correct
12 Correct 0 ms 1084 KB Output is correct
13 Correct 0 ms 1084 KB Output is correct
14 Correct 0 ms 1084 KB Output is correct
15 Correct 0 ms 1084 KB Output is correct
16 Correct 0 ms 1084 KB Output is correct
17 Correct 0 ms 1084 KB Output is correct
18 Correct 0 ms 1084 KB Output is correct
19 Correct 0 ms 1084 KB Output is correct
20 Correct 0 ms 1084 KB Output is correct
21 Correct 0 ms 1084 KB Output is correct
22 Correct 0 ms 1084 KB Output is correct
23 Correct 0 ms 1084 KB Output is correct
24 Correct 0 ms 1084 KB Output is correct
25 Correct 0 ms 1084 KB Output is correct
26 Correct 0 ms 1084 KB Output is correct
27 Correct 0 ms 1084 KB Output is correct
28 Correct 0 ms 1084 KB Output is correct
29 Correct 0 ms 1084 KB Output is correct
30 Correct 0 ms 1084 KB Output is correct