Submission #966449

#	Time	Username	Problem	Language	Result	Execution time	Memory
966449		jcelin	Semafor (COI20_semafor)	C++14	100 / 100	203 ms	724 KiB

semafor

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

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

vi vec = {10, 2, 9, 7, 18, 21, 12, 3, 29, 23}, svi;
int brojb, csz;

struct mat{
	int n;
	vector<vi> a;
	
	void res(int _n){
		n = _n;
		a.clear();
		a.resize(n, vi(n, 0));
	}
	
	void jed(){
		for(int i=0; i<n; i++) a[i][i] = 1;
	}
	
	void prin(){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++) cout << a[i][j] << " ";
			cout << "\n";
		}
	}
}popc, rj, zamul;

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

int add(int a, int b){
	a += b;
	if(a >= mod) a -= mod;
	return a;
}

int exp(int b, ll e){
	int ret = 1;
	while(e){
		if(e & 1) ret = mul(ret, b);
		b = mul(b, b);
		e /= (ll)2;
	}
	return ret;
}

int divide(ll a, ll b){
	return mul(a, exp(b, mod - 2));
}

int ch[12][12];

void pre(){
	for(int i=0; i<12; i++){
		ch[i][0] = 1;
		for(int j=1; j<=i; j++){
			ch[i][j] = add(ch[i - 1][j], ch[i - 1][j - 1]);
		}
	}
}

mat operator *(mat &a, mat &b){
	int n = a.n;
	mat c;
	c.res(n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				c.a[i][j] = add(c.a[i][j], mul(a.a[i][k], b.a[k][j]));
			}
		}
	}
	return c;
}

void pripremi(){
	popc.res(brojb + 1);
	for(int i=0; i<=brojb; i++){
		if(i != brojb) popc.a[i][i + 1] = brojb - i;
		if(i) popc.a[i][i - 1] = i;
	}
}

mat expm(mat b, ll e){
	mat ret;
	ret.res(b.n);
	ret.jed();
	while(e){
		if(e & 1) ret = ret * b;
		b = b * b;
		e /= (ll)2;
	}
	return ret;
}

void pripremi2(){
	zamul.res(csz);
	for(int i=0; i<csz; i++){
		for(int j=0; j<csz; j++){
			int c = __builtin_popcount(vec[i] ^ vec[j]);
			zamul.a[i][j] = divide(popc.a[0][c], ch[brojb][c]);
		}
	}
}

void mnozi(ll e1, ll e2){
	pripremi();
	popc = expm(popc, e1);
	pripremi2();
	zamul = expm(zamul, e2);
	rj = rj * zamul;
}

void solve(){
	ll n, m, k, x;
	cin >> m >> n >> k >> x;
	
	brojb = 5 * m;
	if(m == 1) csz = 10;
	else{
		csz = 100;
		for(int i=0; i<csz; i++){
			int a = vec[i / 10];
			int b = vec[i % 10];
			svi.PB((a << 5) | b);
		}
		swap(svi, vec);
	}
	
	rj.res(csz);
	rj.a[x][x] = 1;
	
	mnozi(k, n / k);
	if(n % k) mnozi(n % k, 1);
	
	for(int i=0; i<csz; i++) cout << rj.a[x][i] << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	pre();
	solve();
	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