repeat_麦森数_变式

//
题解: 并查集 + 高精度快速幂等比数列的前 n 项和 Sn== n*a1;                   // q==1== a1*( 1-q^n )/( 1-q );   // q!=1代入 q=2 转化成 2^n-1 的 后 100 位 ( 类似麦森数 )

//
#include<bits/stdc++.h>
using namespace std;const int N=1e4+5;
const int M=1e5+6;
const int MAXN=100;int father[N];          // 记录 父节点
int cnt[N];             // 记录 家族人数 ( 同校人数 )
int priority[N];        // 根据 cnt[] 建立连通优先级
int ans[ MAXN+11 ];     // 快速幂结果
int sq[ MAXN+11 ];      // 负责 降幂
int max_cnt;            // 记录 最大人数void init()
{memset( father,0,sizeof( father ) );memset( cnt,0,sizeof( cnt ) );memset( priority,0,sizeof( priority ) );memset( ans,0,sizeof( ans ) );memset( sq,0,sizeof( sq ) );max_cnt=0;ans[0]=1;           // !sq[0]=2;            // !
}int my_find( int n )
{return father[n]==n ? n : father[n]=my_find( father[n] );
}// 不重复连通 + 根节点处做加法 + 先发制人 保证获得真实人数
int my_link( int a,int b )
{int ra=my_find(a),rb=my_find(b);if( ra==rb ) return cnt[ra];               // 保证不重复连通    //if( priority[ra]>=priority[rb] ){father[rb]=ra;cnt[ra]+=cnt[rb];                                   // 根节点处做加法 if( priority[ra]==priority[rb] ) priority[ra]++;    // 先发制人return cnt[ra];}else{father[ra]=rb;cnt[rb]+=cnt[ra];return cnt[rb];}
}void bigmul( int a[],int b[] )
{int i,j,temp[ MAXN+11 ];memset( temp,0,sizeof( temp ) );for( i=0;i<MAXN+5;i++ ){for( j=0;i+j<MAXN+5;j++ ){temp[i+j]+=a[i]*b[j];}}for( i=0;i<MAXN+5;i++ ){temp[i+1]+=temp[i]/10;a[i]=temp[i]%10;}
}void fastpow( int n )
{while( n ){if( n&1 ) bigmul( ans,sq );bigmul( sq,sq );n>>=1;}
}int main()
{int n,m,a,b,i;while( ~scanf("%d%d",&n,&m) ){init();for( i=1;i<=n;i++ ){father[i]=i;cnt[i]=1;priority[i]=0;}while( m-- ){scanf("%d%d",&a,&b);max_cnt= max( max_cnt , my_link( a,b ) );}fastpow( max_cnt );for( i=MAXN-1; ans[i]==0 && i ;i-- );       // ans[i]==0 && ifor( ;i;i-- ) printf("%d",ans[i]);printf("%d\n",ans[i]-1);                    // ans[i]-1}return 0;
}

//
find:
01 并查集 + ( 等比数列的前 n 项和 -> 麦森数 -> 高精度快速幂 )
02 ans[0]=1; sq[0]=2; init
03 ans[i]==0 && i
04 ans[i]-1