? ? ? ?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\n",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\n",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\n",rand()%G[a].n+1,G[a].n+rand()%G[b].n+1);if(c)printf("%d %d\n",rand()%G[b].n+1+G[a].n,rand()%G[c].n+G[b].n+G[a].n+1);if(d)printf("%d %d\n",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\n"); 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; }

?

轉載于:https://www.cnblogs.com/rrsb/p/8885627.html

總結

以上是生活随笔為你收集整理的UR 6 智商锁的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。