【UR #6】智商锁

UOJ #75.

随机化,rand出来好多图,然后用4个拼起来试图拼成满足条件的,然后就可以了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cstring>
#include <unordered_map>

#define X first
#define Y second
#define mp std::make_pair
#define pb push_back
#define MOD 998244353
typedef std::pair<int, int> pii;

int ksm(int x, int y){
	int z = 1;
	for(; y; y >>= 1, x = 1ll*x*x%MOD)
		if(y & 1) z = 1ll*x*z%MOD;
	return z;
}

struct Graph{
	int a[15][15], res, n;
	
	void random(int _n){
		n = _n;
		for(int i = 1; i <= n; i++)
			for(int j = i + 1; j <= n; j++)
				a[i][j] = a[j][i] = (rand() % 10 > 7) ? 0 : 1;
	}
	
	void calc(){
		static int b[15][15];
		memset(b, 0, sizeof(b));
		res = 1;
		for(int i = 1; i <= n; i++)
			for(int j = i + 1; j <= n; j++) if(a[i][j])
				b[i][j]--, b[j][i]--, b[i][i]++, b[j][j]++;
		for(int i = 1; i < n; i++){
			for(int j = i + 1; j < n; j++) while(b[j][i]){
				int t = b[i][i] / b[j][i];
				for(int k = i; k < n; k++)
					b[i][k] = (b[i][k] - 1ll * t * b[j][k] % MOD) % MOD;
				std::swap(b[i], b[j]);
				res = -res;
			}
			res = 1ll * res * b[i][i] % MOD;
		}
		if(res < 0) res += MOD;
	}
}a[1010];
int K;

std::unordered_map<int, pii> id;

int main(){
	srand(time(NULL));
	int T;
	scanf("%d", &T);
	while(T--){
		id.clear();
		scanf("%d", &K);
		if(K == 0){
			printf("48 0\n");
			continue;
		}
		int tot = K <= 500 ? 700 : 800;
		for(int i = 1; i <= tot; i++){
			a[i].random(12);
			a[i].calc();
		}
		for(int i = 1; i <= tot; i++)
			for(int j = i; j <= tot; j++){
				int now = 1ll * a[i].res * a[j].res % MOD;
				id[now] = mp(i, j);
			}
		for(int i = 1; i <= tot; i++)
			for(int j = i; j <= tot; j++){
				int now = 1ll * a[i].res * a[j].res % MOD;
				now = 1ll * ksm(now, MOD - 2) * K % MOD;
				if(id.find(now) != id.end()){
					std::vector<pii> ed; ed.clear();
					int ans[4] = {id[now].X, id[now].Y, i, j};
					ed.pb(mp(1, 13)); ed.pb(mp(1, 25)); ed.pb(mp(1, 37));
					for(int t = 0; t < 4; t++){
						for(int x = 1; x <= 12; x++)
							for(int y = x + 1; y <= 12; y++) if(a[ans[t]].a[x][y])
								ed.pb(mp(12*t + x, 12*t + y));
					}
					printf("%d %ld\n", 48, ed.size());
					for(auto w: ed)
						printf("%d %d\n", w.X, w.Y);
					goto qaq;
				}
			}
		qaq:;
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注