Submission #1333893

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

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,base=2;
struct mat
{
    vector<vector<int>> m;
    mat(int x)
    {
        m.resize(3);
        m[0].resize(3,0);
        m[1].resize(3,0);
        m[0][0]=x;
        m[1][1]=x;
    }
    mat operator*(const mat b)
    {
        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[k][j]*b.m[i][k]%mod)%mod;
                }
            }
        }
        return c;
    }

};
int power(int a,int b)
{
    int sol=1;
    while(b)
    {
        if(b&1) sol=sol*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return sol;
}
mat power_mat(mat a,int b)
{
    mat sol(1);
    while(b)
    {
        if(b&1) sol=sol*a;
        b=b/2;
        a=a*a;
    }
    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_mat(base,n);
    ///cout<<base.m[1][1]<<'\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