「UR #6」智商锁 - 随机 + Matrix-Tree

给出$k$，请你构造一个结点数不超过 $100$ 的无向图，使得这个无向图中生成树的个数对$998244353$取模后恰好等于$k$

$k\in [0, 998244353)$

Links

UOJ75

Solution

很妙的一道题啊

首先需要知道这么一个结论：

把生成树个数为$a_1,a_2...a_n$的$n$个图通过相邻两个图任意两个点连一条边的方法串联起来后，得到新图的生成树个数为$\prod_{i=1}^{n}a_i$

这个正确性很显然

接着开始乱搞

那么我们考虑总共随机出$1000$张$12$个点的图，并用Matrix-Tree定理分别求出它们的生成树个数。每张图每条边生成的概率为$0.8$

然后我们试图找出四张图，使得这四张图的生成树个数的乘积为$K$

具体实现的话，显然可以meet in middle，求出任意两张图的生成树个数的乘积和逆元，hash判断一下是否存在

这个算法的正确概率大于$99\%$，具体证明见此

感性理解一下（以下把模数视作$10^9$）

因为每条边选择的概率比较大，且$12$个点的完全图生成树个数为$12^{10}$远大于模数$10^9$，所以生成树个数也会比较大，因此可以近似地看成是模数范围内均匀分布的随机数，这一点与hash类似

所以我们就有了$1000^4=10^{12}$个在$10^9$范围内均匀分布的随机数，用这$10^{12}$个数去覆盖$0$到$10^9$中间的所有数概率还是非常大的

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Mod = 998244353;
const int Maxn = 1e3 + 100;
const int Maxk = 100 + 5;

int N = 1000, K;

inline int Rand (int l, int r) { return rand() % (r - l + 1) + l; }
inline int Rand (int r) { return rand() % r + 1; }

inline int Pow (int a, int b)
{
	int ans = 1;
	for (int i = b; i; i >>= 1, a = (LL)a * a % Mod) if (i & 1) ans = (LL)ans * a % Mod;
	return ans;
}

inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

namespace Matrix
{

	const int Maxn = 12 + 5;

	int A[Maxn][Maxn];

	inline void init () { memset(A, 0, sizeof A); }

	inline void add_edge (int x, int y) { --A[x][y], --A[y][x], ++A[x][x], ++A[y][y]; }

	inline int gauss (int n)
	{
		int ans = 1;
		for (int i =1; i <= n; ++i)
		{
			if (!A[i][i])
			{
				for (int j = i + 1; j <= n; ++j)
					if (A[j][i])
					{
						swap(A[i], A[j]);
						ans = (LL)ans * (Mod - 1) % Mod;
						break;
					}
				if (!ans) return 0;
			}

			int inv = Pow(A[i][i], Mod - 2);
			for (int j = i + 1; j <= n; ++j)
			{
				int now = (LL)A[j][i] * inv % Mod;
				for (int k = i; k <= n; ++k) Add (A[j][k], Mod - (LL)A[i][k] * now % Mod);
			}
		}

		for (int i = 1; i <= n; ++i) ans = (LL)ans * A[i][i] % Mod;

		return ans;
	}
}

struct info
{
	int G[Maxk][Maxk], sum1, sum2, n;

	inline void init () { memset(G, 0, sizeof G); n = 0; }

	inline void build ()
	{
		n = 12;
		Matrix :: init();
		for (int i = 1; i < 12; ++i)
			for (int j = i + 1; j <= 12; ++j)
			{
				if (Rand(1, 10) <= 8) G[i][j] = 1, Matrix :: add_edge (i, j);
				G[j][i] = G[i][j];
			}
		sum1 = Matrix :: gauss (n - 1);
		sum2 = Pow(sum1, Mod - 2);
	}

	inline void print ()
	{
		int m = 0;
		for (int i = 1; i < n; ++i)
			for (int j = i + 1; j <= n; ++j)
				if (G[i][j]) ++m;

		printf("%d %d\n", n, m);
		for (int i = 1; i < n; ++i)
			for (int j = i + 1; j <= n; ++j)
				if (G[i][j]) printf("%d %d\n", i, j);
	}

} A[Maxn];

#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

const int Maxs = Maxn * Maxn;

pair <int, pii> Map1[Maxs];
__gnu_pbds :: gp_hash_table <int, pii > Map2;

int state_cnt;

inline void merge (info &x, info y)
{
	for (int i = 1; i <= y.n; ++i)
		for (int j = 1; j <= y.n; ++j)
			x.G[x.n + i][x.n + j] = y.G[i][j];
	
	x.G[x.n][x.n + 1] = x.G[x.n + 1][x.n] = 1;
	x.n += y.n;
}

inline void Print (int a, int b, int c, int d)
{
	info ans; ans.init();

	merge (ans, A[a]); merge (ans, A[b]);
	merge (ans, A[c]); merge (ans, A[d]);

	ans.print();
}

inline void Solve ()
{
	if (!K) { puts("2 0"); return ; }

	for (int i = 1; i <= state_cnt; ++i)
	{
		int x = Map1[i].y.x, y = Map1[i].y.y, val1 = Map1[i].x;
		int val2 = (LL)K * val1 % Mod;
		if (Map2[val2].x)
		{
	//		printf("%d %d %d %d\n", A[x].sum1, A[y].sum1, A[Map2[val2].x].sum1, A[Map2[val2].y].sum1);
	//		printf("%lld\n", (LL)A[x].sum1 * A[y].sum1 % Mod * A[Map2[val2].x].sum1 % Mod * A[Map2[val2].y].sum1 % Mod);
			Print(x, y, Map2[val2].x, Map2[val2].y);
			return ;
		}
	}
}

inline void Input ()
{
	K = read<int>();
}


inline void Init ()
{
	srand(time(0));

	for (int i = 1; i <= N; ++i) A[i].build ();

	for (int i = 1; i <= N; ++i)
		for (int j = i; j <= N; ++j)
		{
			Map1[++state_cnt] = mp((LL)A[i].sum2 * A[j].sum2 % Mod, mp(i, j));
			Map2[(LL)A[i].sum1 * A[j].sum1 % Mod] = mp(i, j);
		}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("moonfly.in", "r", stdin);
	freopen("moonfly.out", "w", stdout);
#endif

	Init();
	int Testcase = read<int>();

	while (Testcase--)
	{
		Input();
		Solve();
	}

	return 0;
}