oj.uz

Submission #19312

# Submission time Handle Problem Language Result Execution time Memory
19312 2016-02-24T09:26:19 Z ainta Ω (kriii4_P3) C++
100 / 100
 0 ms 1084 KB 
#include<stdio.h>
long long Mod = 1000000007, P, Q, N, K, C[110][2], Res[110];
long long Inv(long long a){
    long long b = Mod - 2, r = 1;
    while(b){
        if(b%2)r=r*a%Mod;
        a=a*a%Mod;b/=2;
    }
    return r;
}
int main(){
    int i;
    scanf("%lld%lld%lld%lld",&P,&Q,&N,&K);
    C[1][0] = 0, C[1][1] = (P-Q)*Inv(P)%Mod;
    for(i=1;i+1<N;i++){
        C[i+1][0] = Q*C[i][0]%Mod*Inv((P-C[i][1]*Q%Mod+Mod)%Mod)%Mod;
        C[i+1][1] = (P-Q)%Mod*Inv((P-C[i][1]*Q%Mod+Mod)%Mod)%Mod;
    }
    Res[N] = 1;
    for(i=N-1;i>=1;i--){
        Res[i] = (Res[i+1]*C[i][1]+C[i][0])%Mod;
    }
    printf("%lld\n",Res[K]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory 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