直接看大犇的帖子没看懂，看别人解读过一次的才明白，题意是找出有多少个联动独立的区间，每有一个独立区间便n—，最后结果为26^(n-区间数)。存在的问题是不能直接用区间的左右数字来查找，因为这样[1,2],[2,3],[3,5]会被记作两个区间，而事实上是三个，因此要以[L-1,R]或[L,R+1]为条件进行查找；其次因为n很大所以要用到快速幂。
代码如下：
#include<stdio.h> #define CONSTANT 1000000007 int father[10000001]; int find(int x) { return x-father[x]?father[x]=find(father[x]):x; } int merge(int x,int y) { int a,b; a=find(x),b=find(y); if(a-b) { father[b]=a; return 1; } return 0; } long long quickPow(long long base,int exp) //底数要用long long，递归返回的数会很大 { long long tmp = 1; if(exp==0) return 1; if(exp==1) return 26; tmp=quickPow(base,exp>>1); tmp=tmp*tmp%CONSTANT; if(exp&1) { tmp = tmp*base % CONSTANT; } return tmp; } int main() { int m,n,i,a,b,cnt,exp; while(~scanf("%d%d",&n,&m)) { cnt=0; for(i=0;i<=n;i++) father[i]=i; for(i=0;i<m;i++) { scanf("%d%d",&a,&b); if(merge(a-1,b)) cnt++; } exp=n-cnt; printf("%I64d\n",quickPow(26,exp)); } return 0; }
快速幂取模模版如下：
//计算a^b mod n 复杂度log(n) int modexp_recursion(int a,int b,int n) { int t = 1; if (b == 0) return 1; if (b == 1) return a%n; t = modexp_recursion(a, b>>1, n); t = t*t % n; if (b&0x1) { t = t*a % n; } return t; }
原文：http://www.cnblogs.com/zhen94/p/3542019.html