Submission #19602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19602	2016-02-25T00:39:40 Z	exqt	Ω (kriii4_P3)	C++	100 / 100	0 ms	1720 KB

P3

#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;
}

Subtask #1

100.0 / 100.0

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