hdu-3461-Code Lock-并查集+高次幂取模

我们可以仔细想一下。

我们只看一个区间。任何一种情况这个区间有26种变化。

如果总体有n个字符的话，有一个区间的话，那么一共有26^(n-1)种可能。

如果有多个区间的话，每个区间可以看成是独立的，如果有x个区间，那么有26^(n-x)种可能。

但是有些区间比如【1，3】，【4，5】区间和【1，5】区间是相同的。动【1，5】区间的话，就相当于动【1，3】【4，5】区间。

那么就用并查集来查找究竟有几个区间。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
      
        using namespace std; #define INF 99999999 const int maxn =600; const int maxm =360000; const int oo = 1<<29; int f[11000000]; #define mod 1000000007 #define LL __int64 int find(int x) { while(x!=f[x])x=f[x]; return x; } LL mul(LL a,LL b) { if(b==0)return 1; if(b==1)return a; LL c=mul(a,b/2); c=(c*c)%mod; if(b&1)c=(c*a)%mod; return c; } int main() { int n,m,a,b,i; while(~scanf("%d%d",&n,&m)) { for(i=0;i<=n;i++)f[i]=i; LL ans=n; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); a=find(a-1); b=find(b); if(a==b)continue; f[b]=a; ans--; } cout<