Submission #774276

# Submission time Handle Problem Language Result Execution time Memory
774276 2023-07-05T13:35:14 Z vjudge1 Semafor (COI20_semafor) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[55][6][6], dp2[55][100][100], dp3[100][100];
int fact[12];
int mod=1e9+7;
/*
void f(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}*/

int sum(int a, int b){
	return (a+b);
}

int mul(int a, int b){
	return (a*b)%mod;
}

int poww(int a, int b){
	if(b==0) return 1;
	int t=poww(a, b/2);
	t=mul(t, t);
	if(b&1) return mul(a, t);
	return t;
}

int cc(int x){
	return mul(fact[5], poww(mul(fact[x], fact[5-x]), mod-2));
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	f();

	int m, n, k, x; cin >> m >> n >> k >> x;
		
	k = min(k, n);

	for(int i = 0; i < 6; i++){
		if(i>0) dp[0][i][i-1] = i;
		if(i<10) dp[0][i][i+1] = 5-i;
	}

	for(int l=1; l<55; l++){
		for(int i=0; i<6; i++){
			for(int j=0; j<6; j++){
				for(int k=0; k<6; k++){
					dp[l][i][k] = sum(dp[l][i][k], mul(dp[l-1][i][j], dp[l-1][j][k]));
				}
			}
		}
	}

	//1<<x hamlede 3 tekten 4 teke geçiş


	vector<int> p(6);
	p[0]=1;


	for(int i=54; i>=0; i--){
		if(!(k&(1ll<<i))) continue;

		
		vector<int> sp(6);
		for(int l=0; l<6; l++){
			for(int j=0; j<6; j++){
				//if(j==5) cout<<dp[i][l][j];
				sp[j]=sum(sp[j], mul(p[l], dp[i][l][j]));
			}
		}

		swap(sp, p);
	}

	fact[0]=1;

		
	for(int i=1; i<6; i++){
		fact[i] = mul(fact[i-1], i);
	}


	for(int i=0; i<6; i++){

		p[i]=mul( p[i], poww(cc(i) , mod-2));

	}


	array<int, 10> c;
	array<int, 100> d;
	c={10, 8, 18, 28, 9, 31, 6, 24, 23, 29};
	

	for(int i=0; i<10; i++){
		for(int l=0; l<10; l++){
			d[i*10+l] = c[i]*32+c[l];
		}
	}

	if(m==1){

		for(int i = 0; i<10; i++){
			for(int l=0; l<10; l++){
				int pf=0;
				for(int t=0; t<10; t++){
					if((c[i]&(1<<t))!=(c[l]&(1<<t))) pf++;
				}

				dp2[0][i][l] = p[pf];
				//if(i==5) cout<<dp2[0][i][l]<<" "<<l<<"\n";

			}
		}

		for(int i=1; i<55; i++){
			for(int l=0; l<10; l++){
				for(int j=0; j<10; j++){
					for(int k=0; k<10; k++){
						dp2[i][l][k] = sum(dp2[i][l][k], mul(dp2[i-1][l][j], dp2[i-1][j][k]));
					}
				}
			}
		}

		vector<int> aa(10);
		aa[x] = 1;



		for(int i=54; i>=0; i--){
			if(k*(1ll<<i)<=n){
				int s=n/(k*(1ll<<i));
				n-=s*(k*(1ll<<i));
				for(int l=0; l<s; l++){
					vector<int> sf(10);
					for(int j=0; j<10; j++){
						for(int kk=0; kk<10; kk++){

							sf[kk] = sum(sf[kk], mul(dp2[i][j][kk], aa[j]));
						}
					}
					swap(aa, sf);
				}


				
			}
		}	

		vector<int> hm(6);
		hm[0]=1;

		for(int i=54; i>=0; i--){
			if(!(n&(1ll<<i))) continue;
			vector<int> sp(6);
			for(int l=0; l<6; l++){
				for(int j=0; j<6; j++){
					sp[j]=sum(sp[j], mul(hm[l], dp[i][l][j]));
				}
			}

			swap(sp, hm);
		}	

		vector<int> ans(10);


		for(int i=0; i<6; i++){
			hm[i]=mul(hm[i], poww(cc(i), mod-2));
		}

		for(int l=0; l<10; l++){
			for(int i=0; i<10; i++){
				int g=0;

				for(int t=0; t<10; t++){
					if((c[i]&(1<<t))!=(c[l]&(1<<t))) g++;
				}
				ans[i]=sum(ans[i], hm[g]*aa[i]);
			}
		}


		for(auto i: ans) cout<<i<<" ";

	}
	

}

Compilation message

semafor.cpp: In function 'int main()':
semafor.cpp:37:2: error: 'f' was not declared in this scope
   37 |  f();
      |  ^