Submission #987509

#	Time	Username	Problem	Language	Result	Execution time	Memory
987509		activedeltorre	Semafor (COI20_semafor)	C++14	100 / 100	666 ms	1364 KiB

semafor

#include <iostream>

using namespace std;
long long nr1[2300];
long long nr2[2300];
long long biti=5;
long long nmax=9;
long long cif(long long val)
{
    if(val==1)
    {
        return 1;
    }
    else if(val==2)
    {
        return 6;
    }
    else if(val==3)
    {
        return 21;
    }
    else if(val==4)
    {
        return 9;
    }
    else if(val==5)
    {
        return 28;
    }
    else if(val==6)
    {
        return 18;
    }
    else if(val==7)
    {
        return 5;
    }
    else if(val==8)
    {
        return 30;
    }
    else if(val==9)
    {
        return 29;
    }
    else
        return 3;
}
long long getid(long long val)
{
    if(biti==5)
        return cif(val/10)*0+cif(val%10);
    else
         return cif(val/10)*32+cif(val%10);
}
long long mod=1e9+7;
struct kuk
{
    long long mat[105][105];
}m1,m2,m3;
kuk mini;
kuk mini2;
kuk base1,base2;
kuk rasp;
void multi(kuk a,kuk b)
{
    long long i,z,j;
    for(i=0;i<=nmax;i++)
    {
        for(j=0;j<=nmax;j++)
        {
            rasp.mat[i][j]=0;
        }
    }
    for(i=0;i<=nmax;i++)
    {
        for(j=0;j<=nmax;j++)
        {
            for(z=0;z<=nmax;z++)
            {
                rasp.mat[i][j]+=(a.mat[i][z]*b.mat[z][j])%mod;
            }
        }
    }
    for(i=0;i<=nmax;i++)
    {
        for(j=0;j<=nmax;j++)
        {
            rasp.mat[i][j]%=mod;
        }
    }
}
long long invs(long long a,long long exp)
{
    long long prod=1;
    while(exp)
    {
        if(exp%2==1)
        {
            prod=(prod*a)%mod;
        }
        exp=exp/2;
        a=(a*a)%mod;
    }
    return prod;
}
long long differ(long long a,long long b)
{
    return __builtin_popcount(getid(a)^getid(b));
}
long long invsc[25][25];
void precalc()
{
    long long i,j,z;
    for(i=1;i<=20;i++)
    {
        for(j=0;j<=i;j++)
        {
            long long prod=1;
            for(z=1;z<=i;z++)
            {
                prod=(prod*invs(z,mod-2))%mod;
            }
            for(z=1;z<=j;z++)
            {
                prod=(prod*z)%mod;
            }
            for(z=1;z<=i-j;z++)
            {
                prod=(prod*z)%mod;
            }
            invsc[i][j]=prod;
        }
    }
}
long long anticomb(long long x)
{
    return invsc[biti][x];
}
kuk base;
kuk afis;
kuk bigmat;
kuk bigmat2;
void calcbigger()
{
    for(long long i=0;i<=nmax;i++)
    {
        for(long long j=0;j<=nmax;j++)
        {
            bigmat.mat[i][j]=(base.mat[0][differ(i,j)]*anticomb(differ(j,i))%mod);
        }
    }
}
signed main()
{
    long long n,i,j,k,l,m,st,val,z;
    cin>>m>>n>>k>>st;
    if(m==2)
    {
        nmax=99;
        biti=10;
    }
    else
    {
        nmax=9;
        biti=5;
    }
    precalc();
    val=getid(st);
    nr1[val]=1;
    base.mat[0][0]=1;
    base2.mat[0][0]=1;
    for(i=0;i<=biti;i++)
    {
        if(i<biti)
        mini.mat[i][i+1]=(biti-i);
        if(i>=1)
        mini.mat[i][i-1]=i;
    }
    mini2=mini;
    long long k2=k;
    while(k)
    {
        if(k%2==1)
        {
            multi(base,mini);
            base=rasp;
        }
        multi(mini,mini);
        mini=rasp;
        k=k/2;
    }
    long long operbig=n/k2;
    long long opersmall=n%k2;
    while(opersmall)
    {
        if(opersmall%2==1)
        {
            multi(base2,mini2);
            base2=rasp;
        }
        multi(mini2,mini2);
        mini2=rasp;
        opersmall=opersmall/2;
    }
    for(i=0;i<=nmax;i++)
    {
        for(j=0;j<=nmax;j++)
        {
            bigmat2.mat[i][j]=(base2.mat[0][differ(i,j)]*anticomb(differ(i,j))%mod);
        }
    }
    afis.mat[st][st]=1;
    calcbigger();
    while(operbig)
    {
        if(operbig%2==1)
        {
            multi(afis,bigmat);
            afis=rasp;
        }
        operbig=operbig/2;
        multi(bigmat,bigmat);
        bigmat=rasp;
    }
    multi(afis,bigmat2);
    afis=rasp;
    for(i=0;i<=nmax;i++)
    {
        cout<<afis.mat[st][i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

semafor.cpp: In function 'int main()':
semafor.cpp:156:23: warning: unused variable 'l' [-Wunused-variable]
  156 |     long long n,i,j,k,l,m,st,val,z;
      |                       ^
semafor.cpp:156:34: warning: unused variable 'z' [-Wunused-variable]
  156 |     long long n,i,j,k,l,m,st,val,z;
      |                                  ^

• Subtask 1: 6 / 6
• Subtask 2: 15 / 15
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40