UR 6 智商锁

SOL：首先这玩意肯定可以的。应该点集大小为100的图和模数差了好几个数量级，而生成树计数又没有什么优秀的数论性质。我们考虑怎么构造。

我们发现环的生成数为环的大小，有桥边的图为去桥后两边的值相乘。

有一个清蒸的做法是考虑环套环，发现答案还是相乘的。比如一个5个点的环和一个2个点的环成环，那么答案就是5*2*2.

这启发我们把其拆成若干个比较小的数，然后让这张图环套环套环下去，我们随几个mod 模数后的商跑那个O（N^0.25）分解合数的算法，感觉很可做的样子。

但是标算似乎更有理有据点：

我们随1000张小图，计算出其生成树的个数，我们找一个四元组让其等于模数就好了。最后用桥把这四张图串起来就好了。

#include<bits/stdc++.h>
#define LL long long
#define eho(x) for(int i=head[x];i;i=net[i])
#define P mo
#define hamo 30000007
#define mo 998244353
#define int LL
#define SIZ 1007
using namespace std;
inline LL qsm(LL x,LL y=mo-2){
    static LL anw;
    for (anw=1;y;y>>=1,x=x*x%mo) if (y&1) anw=anw*x%mo;
    return anw;
}
struct Graph{
  int n,m,a[30][30];
  int val,e1[1010],e2[1010];
  
  void build(int v,int e){
    n=v;
    for(int i=2;i<=n;i++,e--){
      int x=rand()%(i-1)+1;
      a[x][x]++; a[i][i]++;
      a[i][x]--; a[x][i]--;
      e1[++m]=x; e2[m]=i;
    }
    for(int i=1;i<=e;i++){
      int x=rand()%n+1,y=rand()%n+1;
      while(x==y || a[x][y]) x=rand()%n+1,y=rand()%n+1;
      a[x][x]++; a[y][y]++;
      a[x][y]--; a[y][x]--;
      e1[++m]=x; e2[m]=y;
    }
  }

  void calc(){
    val=1;
    for(int i=1;i<n;i++){
      int k; for(k=i;!a[k][i];k++);
      if(k^1){ for(int j=1;j<n;j++) swap(a[i][j],a[k][j]); val=-val; }
      for(int j=i+1;j<n;j++){
    if(!a[j][i]) continue;
    int t=1LL*a[j][i]*qsm(a[i][i],P-2)%P;
    for(int k=i;k<n;k++)
      a[j][k]=(a[j][k]-1LL*a[i][k]*t)%P;
      }
    }
    for(int i=1;i<n;i++) val=1LL*val*a[i][i]%P;
    val=(val+P)%P;
  }
  void print(int idx){
    for(int i=1;i<=m;i++)
      printf("%d %d
",e1[i]+idx,e2[i]+idx);
  }
}G[5010];
int tot;
inline void print(int a,int b,int c,int d){
  int V=G[a].n+G[b].n+G[c].n+G[d].n,E=G[a].m+G[b].m+G[c].m+G[d].m;
  E+=(!!b)+(!!c)+(!!d);
  printf("%d %d
",V,E);
  G[a].print(0);
  G[b].print(G[a].n);
  G[c].print(G[a].n+G[b].n);
  G[d].print(G[a].n+G[b].n+G[c].n);
  if(b)
    printf("%d %d
",rand()%G[a].n+1,G[a].n+rand()%G[b].n+1);
  if(c)
    printf("%d %d
",rand()%G[b].n+1+G[a].n,rand()%G[c].n+G[b].n+G[a].n+1);
  if(d)
    printf("%d %d
",rand()%G[c].n+1+G[a].n+G[b].n,rand()%G[d].n+G[a].n+G[b].n+G[c].n);
}
#define pii pair<int,int>
map<int,pii> mp;
int n,k,X,Y;
signed main () {
//    srand(unsigned (time(0)));
    int t,tot=1000; 
  for(int i=1;i<=tot;i++)
    G[i].build(12,30),G[i].calc();
  for(int i=1;i<=tot;i++)
    for(int j=i;j<=tot;j++)
      mp[1LL*G[i].val*G[j].val%P]=pii(i,j);
  for(int i=1;i<=tot;i++) mp[G[i].val]=pii(i,0);
//    for (int i=1;i<=SIZ;i++)  {
//     G[i].build(12,30);
//     G[i].calc(); f[i]=G[i].val;}
//    for (int i=1;i<=SIZ;i++)
//     for (int j=i;j<=SIZ;j++)
//       mp[f[i]*f[j]%mo]=make_pair(i,j);
//       int t; 
    scanf("%d",&t); 
    tot=SIZ;
     while(t--){
    int k; scanf("%d",&k);
    if(k==0){
      puts("2 0"); continue;
    }
    int a=0,b=0,c=0,d=0;
    if(mp.count(k)){
      a=mp[k].first; b=mp[k].second;
    }
    else{
      for(int i=1;i<=tot && !c;i++)
        for(int j=1;j<=tot;j++){
      int cur=1LL*k*qsm(1LL*G[i].val*G[j].val%P,P-2)%P;
      if(mp.count(cur)){
        b=i; c=j; a=mp[cur].first; d=mp[cur].second;
        break;
      }
    }
    }
    print(a,b,c,d);
  }
//    scanf("%d",&n);
//    while (n--) {
//      scanf("%d",&k);
//      int ok=1;
//      if (k==0) {
//          printf("2 0
"); continue;
//      }
//      for (int i=1;i<=SIZ;i++) if (ok){
//       for (int j=i;j<=SIZ;j++)
//        if (ok) { 
//           ans=qsm(f[i]*f[j]%mo)*k%mo;
//           if (mp.count(ans))  {
//               X=mp[ans].first; Y=mp[ans].second;
//            print(i,j,X,Y);  
//            ok=0; }
//          }  
//        }
//    } 
    return 0;
}