Hypercube Random Number Generator

As the final project of the Algorithm class, you and Ramen are going to design a new Random Number Generator called Hypercube Random Number Generator(HRNG), which is based on the idea of the hypercube.

What is a hypercube? The Wikipedia said:

In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3, picture below). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of space's dimensions, perpendicular to each other and of the same length.

In the problem, we define a hypercube using a pair $\text{C}(n, p)$ , where $\text{}n$ is the dimensions of the hypercube and $\text{}p$ is the length of each dimension. For example, $\text{C}(2,100)$ is a square which length is 100. Then we set one of its corners as the origin, so we get an $\text{}n$ -dimensional coordinate system. Each point inside the hypercube can be described as an $\text{}n$ -tuple like $(x_1,x_2,\cdots,x_n)$ , and a integer point is that a point that $\forall i\in[1,n], x_i\in\mathbb{N}, 1\le x_i\le p$ . Especially, the origin's coordinate is $(1,\cdots,1)$ .

The principle behind the HRNG is pretty easy. We can use a function $\text{HRNG}(C)$ to represent it. When we call it using a hypercube, it will randomly choose an integer point inside it with the same probability. Assume the point is $x=(x_1,\cdots,x_n)$ , then the HRNG calculates the next value by $(\displaystyle{\prod_{i=1}^{n}x_i \mod p})+1$ . For example, if the hypercube is $\text{C}(2,100)$ , we may obtain $\text{HRNG}(C)=47$ if the point it randomly choosed is $\text{}(73,2)$ .

In the report section, the teacher asked students to analysis their algorithm. Ramen has done the design work, so the review is your task. As an RNG, it should return each possible values with the same probability. In other words, the math expectation of HRNG should equal to the expected value of the discrete uniform distribution of $\text{}[1,p]$ , i.e., $\mathcal{U}\{1,p\}$ . To measure your work, you need to compute the expected value of HRNG using given hypercube $\text{C}(n,p)$ .

#include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 998244353; struct Mat { int n; ll a[105][105]; Mat() { memset(a, 0, sizeof a); } void init() { memset(a, 0, sizeof a); for(int i = 1; i <= n; i++) a[i][i] = 1; } Mat operator * (const Mat &t) const { Mat res; res.n = n; for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * t.a[k][j]) % mod; return res; } Mat operator ^ (ll m) const { Mat res; res.n = n; res.init(); Mat tmp(*this); while(m) { if(m & 1) res = res * tmp; tmp = tmp * tmp; m >>= 1; } return res; } }; ll p, n; ll qpow(ll x, ll n) { ll res = 1; while(n) { if(n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { cin >> n >> p; Mat f, g; f.n = g.n = p; for(int i = 1; i <= p; i++) f.a[1][i] = 1; for(int i = 1; i <= p; i++) for(int j = 1; j <= p; j++) { int x = i - 1, y = j - 1; for(int k = 1; k <= p; k++) if(k * x % p == y) { g.a[i][j]++; } } f = f * (g ^ (n - 1)); ll ans = 0; for(int i = 1; i <= p; i++) ans = (ans + 1ll * i * f.a[1][i]) % mod; ans = ans * qpow(qpow(p, n), mod - 2) % mod; cout << ans << endl; }

详情