G - Graph Reconstruction 可图判定问题
首先应用Havel-hakimi定理判定该度数序列是否可图，队友A掉这道题以后，我学习了一下Havel-hakimi定理，下面简单介绍并且证明一下。
定理应用场景：给出节点的度数序列，判断该序列是否为一个具体图或者简单图的度数序列（与此题背景相符合）
过程描述：对序列进行度数从大到小排序，每次把第一个节点的度数设为k，分给后面的k个节点，操作时进行正确性判定，然后重复此过程直到结束
证明：首先这个过程描述是一个迭代过程，针对序列d假设我把第一个点去掉后设为d1，d1可以构成图并且第一个点的度数可以分配给其他点，那么d也可以构成图，这个描述显然是正确的。那为什么第一个点分不了，就决定这个图没办法构成呢？其实是应用了一种等价思维，假设V1这个点要分给后面的Vi，那如果分给Vj（Vj <= Vi）也可以的话，那么和分给Vi是一样的，因为一旦(V1 - Vj）在图中，那么一定有(Vi - Vk)在图中，因为Vi >= Vk，所以整个序列的度数没有变，他们是等价的。这样通过Havel-hakimi就可以检验并且构造出一种可行解了。
注意：此处的图指的是无方向简单图
这个题目另外一个难点就是判定多解的情况，我听了队友的思路试图用二分图的交错路模拟这个过程，发现这个图可能不是二分图。网上还有人用Havel-hakimi的度数一样，改变连边的情况去构造多解，但我个人认为构造多解是可以的，但是判定唯一解应该不对，Havel-hakimi仅仅是一种通解的构造方法，这个序列针对Havel-hakimi是唯一解，但是并不意味没有别的解。所以我比较倾向于网上找到两条顶点交集为空的边，然后做一次交换，这样做肯定是对的，就是时间复杂度高，需要用bitset去优化。
代码如下：
#include<iostream> #include<algorithm> #include<bitset> #include<cstdio> #include<cstring> using namespace std; int n,G[105][105]; bitset<105 > Bit[105]; struct Degree{ int d,id; bool operator <(const Degree &B)const{ return d > B.d; } }a[105]; bool Havel_Hakimi(){ memset(G,0,sizeof(G)); for(int i=1;i<=n;i++){ G[i][i] = 1; } for(int i=0;i<n;i++){ sort(a,a+n); if(a[0].d == 0) break; // printf("seq = "); // for(int j=0;j<n;j++){ // printf("(%d,%d) ",a[j].d,a[j].id); // } // printf(" "); int u = a[0].id; for(int j=1;j<n;j++){ if(a[0].d == 0){ break; } int v = a[j].id; a[0].d--; a[j].d--; G[u][v] = G[v][u] = 1; if(a[j].d < 0) return false; } if(a[0].d != 0) return false; } for(int i=0;i<n;i++) if(a[i].d) return false; for(int i=1;i<=n;i++){ Bit[i].reset(); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(G[i][j]){ Bit[i][j] = 1; } } } return true; } int u1,v1,u2,v2; bool Multi(){ bitset<105 > tmp; for(int i=1;i<=n;i++){ u1=i; for(int j=i+1;j<=n;j++){ u2=j; v1=v2=0; tmp = Bit[i]&(~Bit[j]); for(int k=1;k<=n;k++){ if(tmp[k] && k!=i){ v1 = k; break; } } tmp = (~Bit[i])&Bit[j]; for(int k=1;k<=n;k++){ if(tmp[k] && k!=j){ v2 = k; break; } } if(v1!=0 && v2!=0) return true; } } return false; } void change(){ G[v1][u1]=G[u1][v1] = 0; G[v2][u2]=G[u2][v2] = 0; G[u1][v2]=G[v2][u1] = 1; G[u2][v1]=G[v1][u2] = 1; } int up[10005],down[10005]; void output(){ int medge = 0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(G[i][j]){ up[medge] = i; down[medge++] = j; } } } printf("%d %d ",n,medge); for(int i=0;i<medge;i++){ if(i != 0) printf(" "); printf("%d",up[i]); } printf(" "); for(int i=0;i<medge;i++){ if(i != 0) printf(" "); printf("%d",down[i]); } printf(" "); } int main(){ while(EOF != scanf("%d",&n)){ for(int i=0;i<n;i++){ scanf("%d",&a[i].d); a[i].id = i+1; } if(Havel_Hakimi() == false){ printf("IMPOSSIBLE "); }else { if(Multi()==true){ printf("MULTIPLE "); output(); change(); output(); }else { printf("UNIQUE "); output(); } } } return 0; }
D - Arnold
这个题目考察的是斐波那契循环节，对知识面的考察，所以简单看了下别人的讲解，以后有机会也许能详细学一下吧
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define LL long long #define ull unsigned long long ull M,N; struct Mar{ int n,m; ull a[4][4]; Mar(int nn,int mm){ n=nn; m=mm; memset(a,0,sizeof(a)); } Mar operator *(const Mar &B)const{ Mar C(n,B.m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]){ for(int k=1;k<=B.m;k++){ C.a[i][k]=(C.a[i][k]+(a[i][j]*B.a[j][k])%M)%M; } } } } return C; } }; Mar E(2,2); Mar B(2,2); Mar MarPow(Mar x,ull y){ Mar res = E; // for(int i=1;i<=2;i++){ // for(int j=1;j<=2;j++){ // cout<<E.a[i][j]<<" "; // }cout<<endl; // }cout<<endl; while(y){ if(y&1LL){ res = res*x; } x = x*x; y/=2LL; } return res; } ull qpow(ull x,ull y,ull Mod){ ull res = 1LL; while(y){ if(y&1LL){ res=(res*x)%Mod; } y/=2LL; x=(x*x)%Mod; } return res; } bool legendre(ull p,ull x){ ull res = qpow(x,(p-1LL)/2LL,p); if(res == 1LL) return true; else return false; } ull p[43860]; bool isp[401000]; int pct; void init(){ pct=0; ull up = 400000; for(ull i=2;i<=up;i++){ if(!isp[i]){ p[pct++] = i; } for(int j=0;j<pct;j++){ ull Max = p[j]*i; if(Max > up) break; isp[Max] = 1; if(i%p[j]==0) break; } } // cout<<pct<<endl; } ull fp[500]; int fct,fe[500]; void getFac(ull n){ fct=0; for(int i=0;i<pct;i++){ if(n==1LL) break; if(p[i]*p[i]>n) break; if(n%p[i]==0){ fp[fct] = p[i]; int ect=0; while(n%p[i]==0){ ect++; n/=p[i]; } fe[fct++]=ect; } } if(n!=1){ fp[fct]=n; fe[fct++]=1; } } ull yz[3000]; ull Calc_Cir(ull P){ int yct = 0; for(ull i=1;i*i<=P;i++){ if(P%i==0){ yz[yct++]=i; ull j = P/i; if(i!=j) yz[yct++]=j; } } sort(yz,yz+yct); for(int i=0;i<yct;i++){ Mar Now = MarPow(B,yz[i]-1); // printf("yz = %llu ",yz[i]); ull u1 = (Now.a[1][1]+Now.a[1][2])%M; ull u2 = (Now.a[2][1]+Now.a[2][2])%M; // printf("u1=%llu,u2=%llu ",u1,u2); if(u1==1LL && u2==0LL) return yz[i]; } return -1; } ull gcd(ull a,ull b){ if(b==0) return a; else return gcd(b,a%b); } int main(){ init(); // printf("%f ",sqrt(4e9)); // sqrt(N) = 63245; while(EOF != scanf("%lld",&N)){ if(N == 2LL){ printf("3 "); continue; } E.a[1][1] = E.a[2][2] = 1LL; B.a[1][1]=B.a[1][2]=B.a[2][1]=1LL; ull ans = 1LL; getFac(N); // cout<<fct<<endl; for(int i=0;i<fct;i++){ ull cir = 1LL; if(fp[i]==2LL) cir = 3LL; else if(fp[i]==3LL) cir = 8LL; else if(fp[i]==5LL) cir = 20LL; else { M = fp[i]; if(legendre(fp[i],5)==true){ cir = Calc_Cir(fp[i]-1LL); }else { cir = Calc_Cir((fp[i]+1LL)*2LL); } } for(int j=1;j<fe[i];j++){ cir = cir*fp[i]; } // printf("cir = %llu ",cir); ans = ans/gcd(ans,cir)*cir; } printf("%llu ",ans/2); } return 0; }