F. 杰哥找对象

题解

设杰哥和猛男分别在结点 $i$ 和结点 $j$ 的期望为 $x_{i,j}$ ，npy 在结点 $C$ ，令与结点 $i$ 直接相连的结点的集合为 $U$ ，与 $j$ 直接相连的结点的集合为 $V$ ，由期望公式可得出下列等式：

x_{i,j}=\begin{cases} \displaystyle \dfrac{1}{|U||V|}\sum\limits_{u\in U}\sum\limits_{v\in V}(x_{u,v}+1+[u=v]) & \text {$i\neq C$} \\ 0 & \text {$i=C$} \end{cases}

化简：

(|U||V|)\ x_{i,j}=\begin{cases} \displaystyle \sum\limits_{u\in U}\sum\limits_{v\in V}(x_{u,v}+1+[u=v]) & \text {$i\neq C$} \\ 0 & \text {$i=C$} \end{cases}

解释：当 $i = C$ 时，即杰哥与 npy 的初始结点在同一点，直接结束，故 $x_{i,j}=0$ 。当 $i\neq C$ 时，即杰哥与 $n p y$ 初始节点不在同一点，我们可以把整个过程分为两步：第一步，是杰哥和猛男用一秒分别走到 $u$ 和 $v$ （就是上面公式中的小括号里的 $1$ ）。第二步，是杰哥和猛男分别从 $u$ 和 $v$ 走到结束（就是上边公式中的 $x_{u,v}$ ）。由于杰哥和猛男走到同一点时，杰哥需要用一秒打败猛男，所以，若 $u = v$ 时，需要再加 $1$ 。因为杰哥有 $∣ U ∣$ 种选择，猛男有 $∣ V ∣$ 种选择，所以一共有 $∣ U ∣ ∣ V ∣$ 种选择，选择任意一种的概率为 $\frac{1}{|U||V|}$ 。

对于任意 $i\in[1,n]$ ， $j\in[1,n]$ ，都可以列出一个等式，于是枚举 $i$ 和 $j$ ，可以得到 $n^{2}$ 个 $n^{2}$ 元一次方程组，再利用高斯消元即可得到所有解。

$\mathcal O(n^4)$ 建立方程组， $\mathcal O({(n^2)}^3)=O(n^6)$ 进行高斯消元，总时间复杂度为 $O (n^{6})$ 。

std:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int MAX=2e5+10, M=2e4+10, inf=0x3f3f3f3f;
const ll INF=1LL*inf*inf;
const int mod33=998244353, mod97=1e9+7;
const double PI=acos(-1);
const double eps=1e-7;
const int drc[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define pb push_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
#define endl "\n"

ll Pow(ll a, ll n, ll mod){
	ll ans=1;
	while(n){
		if(n&1) ans=ans*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans;
}
ll GCD(ll a, ll b){ return b?GCD(b, a%b):a; }



struct modint{  // 定义模意义下的数
    ll x, mod;
    modint(const ll xx, const int mmod=mod33){
        x = xx % mmod, mod = mmod;
        if(x < 0) x += mmod;
    }
    modint(const modint& p) { x=p.x, mod=p.mod; }
    modint& operator= (const modint& p) { x=p.x, mod=p.mod; return *this;}
    modint& operator= (const ll xx) { modint a(xx); *this=a; return *this;}
    modint  operator+ (const modint& p) const { modint ans(x + p.x); return ans;}
    modint  operator- (const modint& p) const { modint ans(x - p.x); return ans;}
    modint  operator* (const modint& p) const { modint ans(x * p.x); return ans;}
    modint  operator/ (const modint& p) const { modint ans(x * Pow(p.x, mod-2, mod)); return ans;}
    modint  operator+ (const ll p) const { return modint(*this + modint(p));}
    modint  operator- (const ll p) const { return modint(*this - modint(p));}
    modint  operator* (const ll p) const { return modint(*this * modint(p));}
    modint  operator/ (const ll p) const { return modint(*this / modint(p));}
};
istream& operator>> (istream& in , modint& p) { in >> p.x; return in ; }
ostream& operator<< (ostream& out, const modint& p) { out<< p.x; return out; }
ll fabs(const modint& p) { return p.x ;}

template<class T>
    struct Matrix{ // 矩阵类
        int n, m; // 0 ~ n-1
        vector<vector<T> > a;
        Matrix(const int row = 1, const int col = 1) {
            n = row, m = col;
            a = vector<vector<T> >(n, vector<T>(m, {0}));
        }
        Matrix(const Matrix& p){ n = p.n, m = p.m, a = p.a; }
        Matrix<T>& operator= (const Matrix<T>& p) { n = p.n, m = p.m, a = p.a; return *this;}
        Matrix<T> operator+ (const Matrix<T>& p) const{
            Matrix<T> ans(n, m);
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < m; ++j)
                    ans.a[i][j] = a[i][j] + p.a[i][j];
            return ans;
        }
        Matrix<T> operator- (const Matrix<T>& p) const{
            Matrix<T> ans(n, m);
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < m; ++j)
                    ans.a[i][j] = a[i][j] - p.a[i][j];
            return ans;
        }
        Matrix<T> operator* (const Matrix<T>& p) const{
            Matrix<T> ans(n, p.m);
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < p.m; ++j)
                    for(int k = 0; k < m; ++k)
                        ans.a[i][j] = ans.a[i][j] + a[i][k] * p.a[k][j];
            return ans;
        }
        Matrix<T> operator^ (ll p) const{
            Matrix<T> ans(n, n), b(*this);
            for(int i = 0; i < n; ++i) ans.a[i][i] = 1;
            while(p){
                if(p&1) ans = ans * b;
                b = b * b, p >>= 1;
            } return ans;
        }
        Matrix<T> GetInv() const{
            Matrix<T> b(*this);
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < n; ++j)
                    b.a[i].pb((j==i) ? T(1) : T(0));
            for (int i = 0, k = 0; i < n; ++i, k = i) {
                for (int j = i + 1; j < n; ++j) if (fabs(b.a[j][i]) > fabs(b.a[k][i])) k = j;
                if (fabs(b.a[k][i]) < eps) { b.n = -1;  return b; }
                swap(b.a[i], b.a[k]);
                for (int j = i + 1; j < (n << 1); ++j) b.a[i][j] = b.a[i][j] / b.a[i][i];
                for (int j = 0; j < n; ++j)
                    if (j != i && fabs(b.a[j][i]) > eps)
                        for (k = i + 1; k < (n << 1); ++k)
                            b.a[j][k] = b.a[j][k] - b.a[i][k] * b.a[j][i];
            }
            for(int i = 0; i < n; ++i){
                for(int j = 0, k = n; j < n; ++j, ++k) b.a[i][j] = b.a[i][k];
                for(int j = 0; j < n; ++j) b.a[i].pop_back();
            } return b;
        }
        T GetDet() const{ // 0 ~ n - 1
            vector<vector<T> > b(this->a);
            T det = 1;
            for (int i = 0, k = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) if (fabs(b[j][i]) > fabs(b[k][i])) k = j;
                if (fabs(b[k][i]) < eps) { det = 0; break; }
                swap(b[i], b[k]);
                if (i != k) det = -det;
                det = det * b[i][i];
                for (int j = i + 1; j < n; ++j) b[i][j] = b[i][j] / b[i][i];
                for (int j = 0; j < n; ++j)
                    if (j != i && fabs(b[j][i]) > eps)
                        for (k = i + 1; k < n; ++k)
                            b[j][k] = b[j][k] - b[i][k] * b[j][i];
            }
            return det ;
        }
        vector<vector<T> > Gauss() const{
        	vector<vector<T> > ans(n, vector<T>(m - n, {0}));
        	Matrix<T> b(*this);
        	for (int i = 0, k = 0; i < n; ++i, k = i) {
                for (int j = i + 1; j < n; ++j) if (fabs(b.a[j][i]) > fabs(b.a[k][i])) k = j;
				if(fabs(b.a[k][i]) < eps) { ans.resize(0); break;}
                swap(b.a[i], b.a[k]);
                for (int j = i + 1; j < m; ++j) b.a[i][j] = b.a[i][j] / b.a[i][i];
                for (int j = 0; j < n; ++j)
                    if (j != i && fabs(b.a[j][i]) > eps)
                        for (k = i + 1; k < m; ++k)
                            b.a[j][k] = b.a[j][k] - b.a[i][k] * b.a[j][i];
            }
            for(int i = 0; i < n; ++i){
                for(int j = n; j < m; ++j)
                	ans[i][j-n] = b.a[i][j];
            }
        	return ans;
        }
    };
    


int n,m,K;
int A,B,C;
vector<int> edge[20];
int a[155];

void Solve(){
	Matrix<modint> a(n*n, n*n+1);
	for(int i=1; i<=n; ++i){ // 构造方程组的增广矩阵
		for(int j=1; j<=n; ++j){
			int row=(i-1)*n+j-1;
			if(i==C){
				a.a[row][row]=modint(1);
				continue;
			}
			a.a[row][row]=modint(edge[i].size()*edge[j].size());
			a.a[row][n*n]=modint(a.a[row][row]);
			for(int si=0; si<edge[i].size(); ++si){
				for(int sj=0; sj<edge[j].size(); ++sj){
					int soni=edge[i][si];
					int sonj=edge[j][sj];
					int col=(soni-1)*n+sonj-1;
					a.a[row][col]=modint(-1);
					if(soni==sonj){
						a.a[row][n*n]=a.a[row][n*n]+modint(1);
					}
				}
			}
		}
	}
	vector<vector<modint> > ans(a.Gauss());
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			if(j!=1) cout<<" ";
			cout<<(ans[(i-1)*n+j-1][0]);
		} cout<<endl;
	}
}
int main(){
	IOS;
	int t=1;
//	cin>>t;
	while(t--){
		cin>>n>>m>>C;
		for(int i=1; i<=m; ++i){
			int u, v; cin>>u>>v;
			edge[u].pb(v);
			edge[v].pb(u);
		}
		Solve();
	}
	return 0;
}

题解 | #F. 杰哥找对象#

F. 杰哥找对象

题解

std: