Submission #774464

#	Time	Username	Problem	Language	Result	Execution time	Memory
774464		vjudge1	Semafor (COI20_semafor)	C++17	100 / 100	532 ms	5380 KiB

semafor

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[55][100][100], dp2[55][100][100], dp3[100][100];
int fact[12];
int mod=1e9+7;
int v;

void f(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}

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

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[v], poww(mul(fact[x], fact[v-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;

	if(m==1) v=5;
	else v=10;
		
	k = min(k, n);

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

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



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


	for(int i=54; i>=0; i--){
		if(!(k&(1ll<<i))) continue;
	//for(auto i: p) cout<<i<<" ";
	//	cout<<"\n";
		
		vector<int> sp(v+1);
		for(int l=0; l<v+1; l++){
			for(int j=0; j<v+1; j++){
				//if(j==5) cout<<dp[i][l][j];
				sp[j]=sum(sp[j], mul(p[l], dp[i][l][j]));
			}
		}

		swap(sp, p);
	}

	//for(auto i: p) cout<<i<<" ";
	fact[0]=1;

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


	for(int i=0; i<v+1; 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, 21, 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=48; i>=0; i--){
			if(k<=n/(1ll<<i)){
				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], mul(hm[g],aa[l]));
			}
		}


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

	}

	if(m==2){

		for(int i = 0; i<100; i++){
			for(int l=0; l<100; l++){
				int pf=0;
				for(int t=0; t<11; t++){
					if((d[i]&(1<<t))!=(d[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<100; l++){
				for(int j=0; j<100; j++){
					for(int k=0; k<100; k++){
						dp2[i][l][k] = sum(dp2[i][l][k], mul(dp2[i-1][l][j], dp2[i-1][j][k]));
					}
				}
			}
		}

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



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

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


				
			}
		}	

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

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

			swap(sp, hm);
		}	

		vector<int> ans(100);


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

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

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


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

	}
	

}

Compilation message (stderr)

semafor.cpp: In function 'void f()':
semafor.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
semafor.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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