【UOJ#75】【UR#15】智商锁 | Mrsrz's blog

随机，矩阵树定理

题目大意：

给定 $k$，要求构造一个点数不超过 $100$ 的无重边无自环的无向图，使得它的生成树个数模 $998244353$ 后恰好为 $k$。输出方案。

题解：

高级的随机做法。

我们如果已经知道有两个图，其生成树个数分别为 $a$ 和 $b$，则可以通过加桥边的方式构造一个生成树个数为 $ab$ 的图。

考虑随机生成 $1000$ 张 $12$ 个点的图，并用矩阵树定理计算出其生成树个数。

然后考虑找到其中 $4$ 张图，使得它们连成的图的生成树个数模意义下恰好为 $k$。

使用中途相遇法，即将两张图的情况存起来，然后枚举两张图的情况，另外两张图直接查询。单次查询是 $10^6\cdot\log 10^6$ 的，可以用 hash 表去掉 $\log$。

考虑该做法的正确性：

$12$ 个结点的图的生成树个数最多 $12^{10}$，远大于模数，故我们可以认为我们生成的生成树个数取模后是在范围内均匀随机的。

我们一共有 $10^{12}$ 个数，这些数都可以认为是均匀随机的。

那么我们就要求这 $10^{12}$ 个数能完全覆盖 $0\sim 998244352$ 的所有数。所有数被覆盖的概率为 $(1-(1-\frac1{998244353})^{10^{12}})^{10^9}$，非常接近 $1$。所以正确性很高。

上述参数 $12$，$1000$ 等都选自 UOJ 官方题解，实际实现时可在保证正确性足够的前提下，根据需要做调整。

Code：

#include<iostream>
#include<cstring>
#include<ctime>
#include<random>
#include<algorithm>
#include<map>
using namespace std;
const int md=998244353;
typedef long long LL;
int T,n;
mt19937 mt(time(0)+*new unsigned);
inline int pow(int a,int b){
    int res=1;
    for(;b;b>>=1,a=(LL)a*a%md)if(b&1)res=(LL)res*a%md;
    return res;
}
struct graph{
    static const int M=26;
    int e[M][M],A[M][M],ans;
    inline void clear(){
        memset(e,0,sizeof e);
        memset(A,0,sizeof A);
        ans=0;
    }
    void addedge(int u,int v){
        e[u][v]=e[v][u]=1;
        A[u][v]=A[v][u]=md-1;
        ++A[u][u],++A[v][v];
    }
    void gauss(){
        ans=1;
        for(int i=2;i<=12;++i){
            int t=0;
            for(int j=i;j<=12&&!t;++j)if(A[j][i])t=j;
            if(!t){ans=0;return;}
            if(t!=i){
                ans=md-ans;
                for(int j=i;j<=12;++j)swap(A[i][j],A[t][j]);
            }
            ans=(LL)ans*A[i][i]%md;
            const int iv=pow(A[i][i],md-2);
            for(int j=i;j<=12;++j)A[i][j]=A[i][j]*(LL)iv%md;
            for(int j=i+1;j<=12;++j){
                for(int p=i+1;p<=12;++p)
                A[j][p]=(A[j][p]-(LL)A[j][i]*A[i][p]%md+md)%md;
                A[j][i]=0;
            }
        }
    }
}G[1005];
void init(){
    for(int i=1;i<12;++i)
    G[1].addedge(i,i+1);
    G[1].gauss();
    for(int T=2;T<=700;++T){
        do{
            G[T].clear();
            for(int i=1;i<12;++i)
            for(int j=i+1;j<=12;++j)
            if(mt()>800000000)G[T].addedge(i,j);
            G[T].gauss();
        }while(G[T].ans==0);
    }
}
vector<pair<int,pair<int,int> > >vc;
void output(int*a){
    vector<pair<int,int> >V;
    for(int s=0;s<4;++s)
    for(int i=1;i<12;++i)
    for(int j=i+1;j<=12;++j)
    if(G[a[s]].e[i][j])V.emplace_back(i+s*12,j+s*12);
    V.emplace_back(12,13),V.emplace_back(24,25),V.emplace_back(36,37);
    cout<<"48 "<<V.size()<<'\n';
    for(auto i:V)cout<<i.first<<' '<<i.second<<'\n';
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    for(int i=1;i<=700;++i)
    for(int j=i;j<=700;++j)
    vc.push_back(make_pair((LL)G[i].ans*G[j].ans%md,make_pair(i,j)));
    sort(vc.begin(),vc.end());
    for(cin>>T;T--;){
        int k;
        cin>>k;
        if(k==0)cout<<"2 0\n";else{
            int a[4]={0};
            bool ok=0;
            for(int i=0;i<(int)vc.size();++i){
                int d=(LL)k*pow(vc[i].first,md-2)%md;
                auto x=lower_bound(vc.begin(),vc.end(),make_pair(d,make_pair(0,0)));
                if(x!=vc.end()&&x->first==d){
                    a[0]=x->second.first,a[1]=x->second.second;
                    a[2]=vc[i].second.first,a[3]=vc[i].second.second;
                    output(a);
                    ok=1;
                    break;
                }
            }
            if(!ok)return 1;
        }         
    }
    return 0;
}