oj.uz

Submission #774460

# Submission time Handle Problem Language Result Execution time Memory
774460 2023-07-05T18:13:52 Z vjudge1 Semafor (COI20_semafor) C++17
0 / 100
 531 ms 5204 KB 
#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;

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[10], poww(mul(fact[x], fact[10-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 < 11; i++){
		if(i>0) dp[0][i][i-1] = i;
		if(i<10) dp[0][i][i+1] = 10-i;
	}

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



	vector<int> p(11);
	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(11);
		for(int l=0; l<11; l++){
			for(int j=0; j<11; 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<11; i++){
		fact[i] = mul(fact[i-1], i);
	}


	for(int i=0; i<11; 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==2){

		for(int i = 0; i<100; i++){
			for(int l=0; l<100; l++){
				int pf=0;
				for(int t=0; t<10; 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<100; 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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 531 ms 5204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 5176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 5176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 531 ms 5204 KB Output isn't correct
2 Halted 0 ms 0 KB -