# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
987500 | activedeltorre | Semafor (COI20_semafor) | C++14 | 2 ms | 612 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
using namespace std;
long long nr1[2300];
long long nr2[2300];
long long biti=10;
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)
{
return cif(val/10)*32+cif(val%10);
}
long long mod=1e9+7;
long long nmax=1023;
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<=10;i++)
{
for(j=0;j<=10;j++)
{
rasp.mat[i][j]=0;
}
}
for(i=0;i<=10;i++)
{
for(j=0;j<=10;j++)
{
for(z=0;z<=10;z++)
{
rasp.mat[i][j]+=(a.mat[i][z]*b.mat[z][j])%mod;
}
}
}
for(i=0;i<=10;i++)
{
for(j=0;j<=10;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;
signed main()
{
long long n,i,j,k,l,m,st,val,z;
cin>>m>>n>>k>>st;
precalc();
val=getid(st);
nr1[val]=1;
base.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;
}
while(k)
{
if(k%2==1)
{
multi(base,mini);
base=rasp;
}
multi(mini,mini);
mini=rasp;
k=k/2;
}
for(i=0;i<=99;i++)
{
cout<<(base.mat[0][differ(st,i)]*anticomb(differ(st,i))%mod)<<'\n';
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |