密码锁 总时间限制: 5000ms 内存限制: 524288kB 描述 世界上有一种圆筒形密码锁，这种锁有n位，每一位是a-z中的任意一个字母，这种锁一共有m个可操作的区间，对于每个区间都可以整体向上转动（可以转动多次）。比如abc向上转一下就是bcd，zab向上转一下就是abc（z向上转就是a）。你可以同时转动每个区间内的密码锁,能够通过转动使之一样的密码锁为同一种密码，问你这个密码锁总共有多少种不同的密码。 （如可以操作2-4这个区间，那么ABBB和AAAA就是同一个密码。） 输入 输入有一系列测试样例，每个测试样例包含两个整数N（1<=N<=100000000）和M（0<=M<=1000000），分别代表圆筒形密码锁的长度和可操作的区间数量。 接下来M行。每行包含两个整数L和R（1<=L<=R<=N），表示一个可操作的区间。 输出 输出不同的密码数，答案对1000000007取模。 样例输入
1 1 1 1 2 1 1 2样例输出
1 26思路点拔：首先，我们走一走样例，第一个就不看了，那么第二个为什么是26种呢？我们可以这么想：首先确定一个区间，然后我们就去算另一个区间可取的情况有多少种，所以26就是这么来的，所以，本题就是用并查集去对输入的两个数作为等价类去进行合并，然后，答案就是26的(n-合并次数)次方，所以，代码应该很明确了，就是要注意：由于本题的数据非常大，所以我们需要进行读入优化，否则会超时，求26的幂就是需要用一个二分思想的快速幂来进行计算，否则也会超时，最后模一下就完事了~，上代码！！！
#include<cstdio> #include<iostream> using namespace std; int tot,n,m; int mo=1000000007; //模数 long long qkpow(int n) //快速幂 { long long i=1,ans=26; while(n>0) { if(n%2==1) //用二分的思想进行快速计算 { i*=ans; i%=mo; //每次算完就要取模 } ans*=ans; ans%=mo; n/=2; //二分 } return i; //返回结果 } int fa[200000005]; //定义fa数组存储每个节点的父亲节点 void makeSet(int n) //初始化 { for(int i=1;i<=n;i++) fa[i]=i; } int find(int n)//寻找根节点 { if(n!=fa[n]) //用递归思求根节点 fa[n]=find(fa[n]); return fa[n]; } void unionSet(int a,int b) //合并 { int x=find(a),y=find(b); //记录两个数的根节点 if(x!=y) //如果根节点不相等 { fa[x]=y; //合并 tot++; //统计合并次数 } } bool read(int &x) //读入优化（在本题，读入优化比scanf快200多毫秒） { int f=1; x=0; char s=getchar(); while(s<'0'||s>'9') //如果输入的东西不是数字 { if(s=='-') //如果是负的 f=-1; //f就等于-1 s=getchar(); //继续读入（getchar()比scanf快得多） } while(s>='0'&&s<='9') //如果是数字 { x=x*10+s-'0'; //继续读入 s=getchar(); } x*=f; } int main() { while(scanf("%d%d",&n,&m)!=EOF) //无限输入 { tot=0; //初始时合并次数为0 makeSet(n);//初始化 int a,b; for(int i=1;i<=m;i++) //输入 { read(a); read(b); unionSet(a-1,b); //合并 } printf("%lld\n",qkpow(n-tot)%mo); //输出结果 } return 0;//结束了 } //思路不难，但是极易超时（我错了45次 >_<），所以一定要注意，因为时间卡得很紧