1 条题解

  • 0
    @ 2026-1-12 22:49:14

    #include <bits/stdc++.h>
    #define EB emplace_back
    using std::cin;
    using std::cout;
    using std::vector;
    
    typedef unsigned int u32;
    typedef unsigned long long u64;
    typedef unsigned __int128 u128, u128set[9];
    typedef std::pair <int, int> pr;
    typedef std::pair <u64, int> pli;
    constexpr u128 one = 1, row_mask = 0x1ffull, col_mask = one << 72 | 0x8040201008040201ull;
    const int basic_res[6][3] = {
    	{0, 1, 2}, {1, 0, 2}, {2, 1, 0}, {0, 2, 1}, {1, 2, 0}, {2, 0, 1}
    };
    const vector <pr> basic_op[6] = {
    	{},
    	{{0, 1}},
    	{{0, 2}},
    	{{1, 2}},
    	{{0, 1}, {1, 2}},
    	{{1, 2}, {0, 1}}
    };
    
    struct permutation {vector <pr> op; int res[9];} p[1296];
    
    u64 compress(u128 x) {
    	static u64 y;
    	x ^= x << 11, x ^= x >> 45, x ^= x << 14, y = x % 0xffffffffffffffc5ull;
    	return y ^= y << 13, y ^= y >> 7, y ^= y << 17, y * 0xb7e151628aed2a6b + 0x243f6a8885a308d3ull;
    }
    
    struct sudoku {
    	char s[9][9];
    	u128set pos, tpos;
    	u128set rowperm[1296], colperm[1296], tcolperm[1296];
    	u64 rowperm_h[1296], colperm_h[1296], tcolperm_h[1296];
    
    	friend std::istream & operator >> (std::istream &in, sudoku &B) {
    		int i; static char buf[20];
    		for (i = 0; i < 9; ++i) in >> buf, memcpy(B.s[i], buf, 9);
    		return in;
    	}
    
    	void init() {
    		int i, j, k; u32 x; u128 part[9][9];
    		memset(pos, 0, 144), memset(tpos, 0, 144);
    		for (i = 0; i < 9; ++i)
    			for (j = 0; j < 9; ++j)
    				if ((x = (u32)s[i][j] - 49u) < 9u)
    					pos[x] |= one << (i * 9 + j),
    					tpos[x] |= one << (i + j * 9);
    		// row
    		for (i = 0; i < 9; ++i)
    			for (j = 0; j < 9; ++j) part[i][j] = pos[i] >> (j * 9) & row_mask;
    		for (k = 0; k < 1296; ++k) {
    			u128set &Z = rowperm[k]; int (&q)[9] = p[k].res;
    			u64 &H = rowperm_h[k]; H = 0;
    			for (i = 0; i < 9; ++i) {
    				for (Z[i] = j = 0; j < 9; ++j) Z[i] |= part[i][q[j]] << (j * 9);
    				H ^= compress(Z[i]);
    			}
    		}
    		// column
    		for (i = 0; i < 9; ++i)
    			for (j = 0; j < 9; ++j) part[i][j] = pos[i] >> j & col_mask;
    		for (k = 0; k < 1296; ++k) {
    			u128set &Z = colperm[k]; int (&q)[9] = p[k].res;
    			u64 &H = colperm_h[k]; H = 0;
    			for (i = 0; i < 9; ++i) {
    				for (Z[i] = j = 0; j < 9; ++j) Z[i] |= part[i][q[j]] << j;
    				H ^= compress(Z[i]);
    			}
    		}
    		// transpose + column
    		for (i = 0; i < 9; ++i)
    			for (j = 0; j < 9; ++j) part[i][j] = tpos[i] >> j & col_mask;
    		for (k = 0; k < 1296; ++k) {
    			u128set &Z = tcolperm[k]; int (&q)[9] = p[k].res;
    			u64 &H = tcolperm_h[k]; H = 0;
    			for (i = 0; i < 9; ++i) {
    				for (Z[i] = j = 0; j < 9; ++j) Z[i] |= part[i][q[j]] << j;
    				H ^= compress(Z[i]);
    			}
    		}
    	}
    
    	pr compare(const sudoku &B) {
    		int i, j, k, a, b, u, v; static pli w[3888]; static u128 buf[18]; static int HC = 0;
    		for (i = 0; i < 1296; ++i)
    			w[i] = pli(rowperm_h[i], i),
    			w[i + 1296] = pli(B.colperm_h[i], i + 0x10000),
    			w[i + 2592] = pli(B.tcolperm_h[i], i + 0x30000);
    		std::sort(w, w + 3888);
    		for (j = i = 0; i < 3888; i = j) {
    			for (k = i - 1; j < 3888 && w[i].first == w[j].first; ++j) if (!(w[j].second & 0x10000)) k = j;
    			if (i == ++k || k == j) continue;
    			for (a = i; a < k; ++a)
    				for (b = k; b < j; ++b) {
    					std::tie(u, v) = pr(w[a].second, w[b].second), v &= 0x2ffff,
    					memcpy(buf, rowperm[u], 144),
    					memcpy(buf + 9, v & 0x20000u ? B.tcolperm[v & 0xffff] : B.colperm[v], 144);
    					std::sort(buf, buf + 9), std::sort(buf + 9, buf + 18);
    					if (!memcmp(buf, buf + 9, 144)) return pr(u, v);
    					fprintf(stderr, "Hash collision %d time(s).\n", ++HC);
    				}
    		}
    		return pr(-1, -1);
    	}
    } a[20];
    
    void gen_permutations() {
    	int I, i, j, k, si, sj, sk, v, o[9], O[3], n = 0; vector <pr> w;
    	for (I = 0; I < 6; ++I) {
    		memcpy(O, basic_res + I, 12), w.clear();
    		for (const pr &e : basic_op[I]) w.EB(~e.first, ~e.second);
    		si = w.size();
    		for (i = 0; i < 6; ++i) {
    			memcpy(o, basic_res + i, 12), w.resize(si);
    			for (const pr &e : basic_op[i]) w.EB(e);
    			sj = w.size();
    			for (j = 0; j < 6; ++j) {
    				memcpy(o + 3, basic_res + j, 12), w.resize(sj);
    				for (const pr &e : basic_op[j]) w.EB(e.first + 3, e.second + 3);
    				sk = w.size();
    				for (k = 0; k < 6; ++k) {
    					memcpy(o + 6, basic_res + k, 12), w.resize(sk);
    					for (const pr &e : basic_op[k]) w.EB(e.first + 6, e.second + 6);
    					for (v = 0; v < 9; ++v) p[n].res[v] = O[v / 3] * 3 + o[v];
    					p[n++].op = w;
    				}
    			}
    		}
    	}
    	assert(n == 1296);
    }
    
    void output(const sudoku &A, const sudoku &B, int perm_a, int perm_b) {
    	int i, j, size = 0; static std::ostringstream os; os.str("");
    	bool final_flip = perm_b & 0x20000; perm_b &= 0xffff;
    	u128set Ai, Bi;
    
    	for (const pr &e : p[perm_a].op)
    		if (++size, e.first >> 31)
    			os << 'R' << ' ' << -e.first << ' ' << -e.second << '\n';
    		else os << 'r' << ' ' << e.first + 1 << ' ' << e.second + 1 << '\n';
    	for (i = p[perm_b].op.size() - 1; i >= 0; --i) {
    		const pr &e = p[perm_b].op[i];
    		if (++size, e.first >> 31)
    			os << 'C' << ' ' << -e.first << ' ' << -e.second << '\n';
    		else os << 'c' << ' ' << e.first + 1 << ' ' << e.second + 1 << '\n';
    	}
    	if (final_flip) ++size, os << 'F' << '\n';
    
    	memcpy(Ai, A.rowperm[perm_a], 144),
    	memcpy(Bi, final_flip ? B.tcolperm[perm_b] : B.colperm[perm_b], 144);
    
    	for (i = 0; i < 8; ++i) {
    		j = std::find(Ai + i, Ai + 9, Bi[i]) - Ai, assert(j != 9);
    		if (i != j)
    			++size, os << 'D' << ' ' << i + 1 << ' ' << j + 1 << '\n',
    			std::swap(Ai[i], Ai[j]);
    	}
    	assert(Ai[8] == Bi[8]);
    
    	cout << size << '\n' << os.str();
    }
    
    int main() {
    	int i, j, u, v, n;
    	std::ios::sync_with_stdio(false), cin.tie(NULL);
    	gen_permutations(), cin >> n;
    	for (i = 0; i < n; ++i) cin >> a[i], a[i].init();
    	for (i = 0; i + 1 < n; ++i)
    		for (j = i + 1; j < n; ++j) {
    			std::tie(u, v) = a[i].compare(a[j]);
    			if (~u) cout << "Yes\n", output(a[i], a[j], u, v);
    			else cout << "No\n";
    		}
    	return 0;
    }
    
    
    • 1

    [NWRRC 2013] Intellectual Property(wuspj)

    信息

    ID
    6160
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    0
    上传者