Submission #987507

#TimeUsernameProblemLanguageResultExecution timeMemory
987507activedeltorreSemafor (COI20_semafor)C++14
12 / 100
117 ms1112 KiB
#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<=99;i++) { for(j=0;j<=99;j++) { rasp.mat[i][j]=0; } } for(i=0;i<=99;i++) { for(j=0;j<=99;j++) { for(z=0;z<=99;z++) { rasp.mat[i][j]+=(a.mat[i][z]*b.mat[z][j])%mod; } } } for(i=0;i<=99;i++) { for(j=0;j<=99;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; void calcbigger() { for(long long i=0;i<=99;i++) { for(long long j=0;j<=99;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; 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<=99;i++) { afis.mat[st][i]=(base2.mat[0][differ(st,i)]*anticomb(differ(st,i))%mod); } calcbigger(); while(operbig) { if(operbig%2==1) { multi(afis,bigmat); afis=rasp; } operbig=operbig/2; multi(bigmat,bigmat); bigmat=rasp; } for(i=0;i<=99;i++) { cout<<afis.mat[st][i]<<'\n'; } return 0; }

Compilation message (stderr)

semafor.cpp: In function 'int main()':
semafor.cpp:152:19: warning: unused variable 'j' [-Wunused-variable]
  152 |     long long n,i,j,k,l,m,st,val,z;
      |                   ^
semafor.cpp:152:23: warning: unused variable 'l' [-Wunused-variable]
  152 |     long long n,i,j,k,l,m,st,val,z;
      |                       ^
semafor.cpp:152:34: warning: unused variable 'z' [-Wunused-variable]
  152 |     long long n,i,j,k,l,m,st,val,z;
      |                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...