Submission #581597

#	Time	Username	Problem	Language	Result	Execution time	Memory
581597		penguinhacker	Semafor (COI20_semafor)	C++17	100 / 100	207 ms	632 KiB

semafor

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int M=1e9+7;

ll bin_pow(ll b, ll p=M-2) {
	ll r=1;
	for (; p; p/=2, b=b*b%M)
		if (p%2)
			r=r*b%M;
	return r;
}

struct Mat {
	int n, m;
	vector<vector<int>> a;
	Mat() {}
	Mat(int n, int m) : n(n), m(m) {a.assign(n, vector<int>(m));}
	vector<int>& operator[](int i) {return a[i];}
	const vector<int>& operator[](int i) const {return a[i];}
	Mat operator*(const Mat& b) const {
		assert(m==b.n); Mat r(n, b.m);
		for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) for (int k=0; k<b.m; ++k) r[i][k]=(r[i][k]+(ll)a[i][j]*b[j][k])%M;
		return r;
	};
};

Mat mat_pow(Mat b, ll p) {
	assert(b.n==b.m);
	int n=b.n;
	Mat r(n, n);
	for (int i=0; i<n; ++i)
		r[i][i]=1;
	for (; p; p/=2, b=b*b)
		if (p%2)
			r=r*b;
	return r;
}

int m, x, mask1[10], mask2[100];
ll n, k, C[11][11];

void init() {
	mask1[0]=1<<1|1<<3;
	mask1[1]=1<<1;
	mask1[2]=1<<0|1<<3;
	mask1[3]=1<<0|1<<1|1<<2;
	mask1[4]=1<<1|1<<4;
	mask1[5]=1<<0|1<<2|1<<4;
	mask1[6]=1<<2|1<<3;
	mask1[7]=1<<0|1<<1;
	mask1[8]=1<<0|1<<2|1<<3|1<<4;
	mask1[9]=1<<0|1<<1|1<<2|1<<4;
	for (int i=0; i<100; ++i)
		mask2[i]=(mask1[i/10]<<5)|mask1[i%10];
	C[0][0]=1;
	for (int i=1; i<=10; ++i)
		for (int j=0; j<=i; ++j)
			C[i][j]=((j?C[i-1][j-1]:0)+C[i-1][j])%M;
}

vector<int> get_changes(ll d) {
	Mat a(1, 5*m+1), t(5*m+1, 5*m+1);
	a[0][0]=1;
	for (int i=0; i<=5*m; ++i) {
		if (i)
			t[i][i-1]=i;
		if (i+1<=5*m)
			t[i][i+1]=5*m-i;
	}
	a=a*mat_pow(t, d);
	return a[0];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();
	cin >> m >> n >> k >> x;
	int dim=m==1?10:100;
	Mat a(1, dim), t(dim, dim);
	a[0][x]=1;
	vector<int> block_changes=get_changes(k);
	for (int i=0; i<dim; ++i)
		for (int j=0; j<dim; ++j) {
			int num1=m==1?mask1[i]:mask2[i];
			int num2=m==1?mask1[j]:mask2[j];
			int dif=__builtin_popcount(num1^num2);
			t[i][j]=(ll)block_changes[dif]*bin_pow(C[5*m][dif])%M;
		}
	a=a*mat_pow(t, n/k);
	vector<int> final_changes=get_changes(n%k);
	vector<ll> ans(dim);
	for (int i=0; i<dim; ++i)
		for (int j=0; j<dim; ++j) {
			int num1=m==1?mask1[i]:mask2[i];
			int num2=m==1?mask1[j]:mask2[j];
			int dif=__builtin_popcount(num1^num2);
			ans[j]=(ans[j]+(ll)a[0][i]*final_changes[dif]%M*bin_pow(C[5*m][dif]))%M;
		}
	for (int i=0; i<dim; ++i)
		cout << ans[i] << "\n";
	return 0;
}

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