Submission #1333898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333898		tudor_costin	Struktura (COCI26_struktura)	C++20	110 / 110	1 ms	344 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
struct mat
{
    array<array<int,2>,2> m{{{0,0},{0,0}}};
    mat(int x=0)
    {
        m[0][0]=x;
        m[1][1]=x;
    }
    mat operator*(const mat b) const
    {
        mat c(0);
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    c.m[i][j]=(c.m[i][j]+m[i][k]*b.m[k][j]%mod)%mod;
                }
            }
        }
        return c;
    }
    mat operator%(const int b) const
    {
        return *this;
    }

};
template<typename T>
T power(T a,int b)
{
    T sol{1};
    while(b)
    {
        if(b&1) sol=sol*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return sol;
}
signed main()
{
    int n,k;
    cin>>n>>k;
    if(k<n)
    {
        cout<<0<<'\n';
        return 0;
    }
    mat base(1);
    base.m={{{0,1},
             {1,1}}};
    base=power(base,n);
    int num=power(k,n);
    int ans=base.m[1][1]*power(num,mod-2)%mod;
    cout<<ans<<'\n';
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 17 / 17
• Subtask 2: 23 / 23
• Subtask 3: 19 / 19
• Subtask 4: 25 / 25
• Subtask 5: 26 / 26