답안 #19602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19602 2016-02-25T00:39:40 Z exqt Ω (kriii4_P3) C++
100 / 100
0 ms 1720 KB
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <cstring>
#include <map>
using namespace std;

#define in cin
#define out cout
#define ll long long int

ll DV = 1000000007;
ll pow(ll a, ll b)
{
    ll t = a;
    ll res = 1;
    while(b)
    {
        if(b%2) res = (res * t) % DV;
        t = t % DV;
        t = (t*t) % DV;
        b = b >> 1;
    }

    return res;
}

ll inv(ll a)
{
    return pow(a, DV-2)%DV;
}

ll mul(ll a, ll b)
{
    return (a%DV)*(b%DV)%DV;
}

struct mat22
{
    ll a1, a2, a3, a4;
    mat22 operator*(const mat22 &T)
    {
        return {mul(a1, T.a1)+mul(a2, T.a3), mul(a1, T.a2)+mul(a2, T.a4),
            mul(a3, T.a1)+mul(a4, T.a3), mul(a3, T.a2)+mul(a4, T.a4)};
    }
    void print()
    {
        out << a1 << " " << a2 << " " << a3 << " " << a4 << endl;
    }
};

int main()
{
    ll A, B; in >> A >> B;
    B = A-B;
    ll p = B*inv(A);
    ll q = (A-B)*inv(A);
    mat22 T = {inv(p), mul(-q, inv(p)) + DV, 1, 0};

    ll N, K; in >> N >> K;
    ll a1, a2, a0 = 0;

    mat22 MT = {1,0,0,1};
    for(int i=2; i<=N; i++)
    {
        MT = MT * T;
    }

    a1 = inv(MT.a1);

    if(K == 0) out << 0;
    else if(K == N) out << 1;
    else
    {
        for(int i=1; i<K; i++)
        {
            a2 = mul( T.a1, a1 ) + mul( T.a2, a0 );
            a2 %= DV;
            a0 = a1 % DV;
            a1 = a2 % DV;
        }

        out << a1;
    }

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1720 KB Output is correct
2 Correct 0 ms 1720 KB Output is correct
3 Correct 0 ms 1720 KB Output is correct
4 Correct 0 ms 1720 KB Output is correct
5 Correct 0 ms 1720 KB Output is correct
6 Correct 0 ms 1720 KB Output is correct
7 Correct 0 ms 1720 KB Output is correct
8 Correct 0 ms 1720 KB Output is correct
9 Correct 0 ms 1720 KB Output is correct
10 Correct 0 ms 1720 KB Output is correct
11 Correct 0 ms 1720 KB Output is correct
12 Correct 0 ms 1720 KB Output is correct
13 Correct 0 ms 1720 KB Output is correct
14 Correct 0 ms 1720 KB Output is correct
15 Correct 0 ms 1720 KB Output is correct
16 Correct 0 ms 1720 KB Output is correct
17 Correct 0 ms 1720 KB Output is correct
18 Correct 0 ms 1720 KB Output is correct
19 Correct 0 ms 1720 KB Output is correct
20 Correct 0 ms 1720 KB Output is correct
21 Correct 0 ms 1720 KB Output is correct
22 Correct 0 ms 1720 KB Output is correct
23 Correct 0 ms 1720 KB Output is correct
24 Correct 0 ms 1720 KB Output is correct
25 Correct 0 ms 1720 KB Output is correct
26 Correct 0 ms 1720 KB Output is correct
27 Correct 0 ms 1720 KB Output is correct
28 Correct 0 ms 1720 KB Output is correct
29 Correct 0 ms 1720 KB Output is correct
30 Correct 0 ms 1720 KB Output is correct