Submission #773989

#	Time	Username	Problem	Language	Result	Execution time	Memory
773989		vjudge1	Semafor (COI20_semafor)	C++17	18 / 100	121 ms	43880 KiB

semafor

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 2005
#define int long long
#define A array<array<int, 100>, 100>

const int modulo = 1e9 + 7;
int dp[40][2005][40], fac[N], infac[N], comb[N][N], dist[10][10];
A distt, distt2, zero;


int add(int a, int b){
	if (a + b < modulo) return a + b;
	return a + b - modulo;
}

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

int fe(int a, int b){
	if (b == 0) return 1;
	if (b % 2) return mul(a, fe(a, b - 1));
	int tmp = fe(a, b / 2);
	return mul(tmp, tmp);
}


void mat_mul(A &a, A &b, A &c)
{
	for (int i = 0; i < 100; i++){
		for (int j = 0; j < 100; j++){
			c[i][j] = 0;
			for (int k = 0; k < 100; k++){
				c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
			}
		}
	}
}


void mat_fe(A &a, int b, A &c){
	if (b == 0){
		for (int i = 0; i < 100; i++)
			c[i][i] = 1;
		return;
	}
	if (b == 1){
		c = a;
		return;
	}

	A tmp = zero;
	if (b % 2){
		mat_fe(a, b - 1, tmp);
		mat_mul(a, tmp, c);
		return;
	} 

	mat_fe(a, b / 2, tmp);
	mat_mul(tmp, tmp, c);
}


int32_t main(){
	//fileio();
	fastio();

	fac[0] = 1, infac[0] = 1;
	for (int i = 1; i < N; i++){
		fac[i]= mul(fac[i - 1], i);
		infac[i] = mul(infac[i - 1], fe(i, modulo - 2));
	}


	for (int i = N - 1; i >= 0; i--){
		for (int j = i; j >= 0; j--){
			comb[i][j] = mul(fac[i], mul(infac[j], infac[i - j]));
		}
	}
	vector<int> tmp[10];
	vector<int> req(10, 0);
	int a = 0, b = 1, c = 2, d = 3, e = 4;
	tmp[0] = {d, b};
	tmp[1] = {b};
	tmp[2] = {a, d};
	tmp[3] = {c, b, a};
	tmp[4] = {e, b};
	tmp[5] = {a, e, c};
	tmp[6] = {d, c};
	tmp[7] = {a, b};
	tmp[8] = {a, c, d, e};
	tmp[9] = {a, e, b, c};


	for (int i = 0; i < 10; i++){
		for (auto j : tmp[i])
			req[i] |= (1<<j);
	}

	int dist[10][10];
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++){
			for (int k = 0; k < 5; k++){
				if ((1<<k) & (req[i] ^ req[j])) dist[i][j]++;
			}
		}
	}


	int n, m, k, x;
	cin>>m>>n>>k>>x;
	for (int i = 0; i < 32; i++){
		dp[i][0][i] = 1;
		for (int j = 1; j <= k; j++)
		{
			for (int l = 0; l < 32; l++){
				for (int x = 0; x < 5; x++){
					dp[i][j][l] = add(dp[i][j][l], dp[i][j - 1][l ^ (1<<x)]);
				}
			}
		}
	}


	int maks = 10;
	if (m == 2) maks = 100;
	for (int i = 0; i < maks; i++){
		for (int j = 0; j < maks; j++){
			if (m == 2){
				for (int l = 0; l <= k; l++)
					distt[i][j] = add(mul(comb[k][l], mul(dp[req[i % 10]][l][req[j % 10]], dp[req[i / 10]][k - l][req[j / 10]])), distt[i][j]);	
			}
			else distt[i][j] = dp[req[i % 10]][k][req[j % 10]];
			//cout<<i<<sp<<j<<sp<<distt[i][j]<<endl;
		}
	}

	int gh = n % k;
	for (int i = 0; i < maks; i++){
		for (int j = 0; j < maks; j++){
			if (m == 2){
				for (int l = 0; l <= gh; l++)
					distt2[i][j] = add(mul(comb[k][l], mul(dp[req[i % 10]][l][req[j % 10]], dp[req[i / 10]][gh - l][req[j / 10]])), distt2[i][j]);	
			}
			else distt2[i][j] = dp[req[i % 10]][gh][req[j % 10]];
			//cout<<i<<sp<<j<<sp<<distt2[i][j]<<endl;
		}
	}

	A res = zero, res2 = zero;
	//cout<<n / k<<endl;
	mat_fe(distt, n / k, res);
	

	if (gh > 0) 
		mat_mul(res, distt2, res2);
	else res2 = res;

	for (int i = 0; i < maks; i++){
		cout<<res2[x][i]<<endl;
	}


	//cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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