hdu3461 找規律+并查集

http://acm.hdu.edu.cn/showproblem.php?pid=3461

題意：給出一個由N NN個字母組成的鎖。給出M MM個區間[L,R] [L,R][L,R]，每次操作可以将某個區間中所有字母變為字典序中的下一個字母。特殊地，‘z’會變成’a’。如果一把鎖通過對可操作區間的有限次操作可以得到另一個鎖，那麼認為這兩個鎖是相同的。請求出一共有多少種不同的鎖%(1e9+7)

解法：就是慢慢推廣。

1. 一個區間都沒有，不同的方案數就是26^n
2. 隻有一個區間[1,1]，不同的方案數應該是26^(n-1)
3. 隻有一個區間[1,3]，不同的方案數還是26^(n-1)。為啥呢？假設第一位開始是a，我們可以通過旋轉時的這一位變成任意的字元。那前三位不同的鎖的情況是多少？是第2位的26*第3位的26。隻有第一位的計算跳過去了。
4. 對于不相交區間[1,3] [4,5]這個肯定是26^(n-2)
5. 對于相交的區間[1,3][3,5],第2位需要将結果*26,第三位是不需要的。因為假設第三位一開始為a，可以通過旋轉[3,5]區間使得第3位任意的變化。是以結果還是26(n-2)
6. 對于區間[1,3],[4,5][1,5]。[1,5]可以通過[1,3][4,5]的操作來實作。是以[1,5]是不需要的。當然[1,4][3,5][1,5]這樣的三個區間還都是有效的。 
7. 是以結果就是26^(n-cnt)%mod  cnt就是無效的區間的個數  

問題就轉換成了找到[1,3][4,5][1,5]這樣的區間，然後去掉[1,5]。記錄[1,5]這樣區間的個數cnt。結果就是26^(n-cnt)%mod

怎樣記錄呢？非常巧妙的用了并查集！unit(l,r+1) 注意是r+1。然後判重就行。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll mod=1e9+7;
const int maxn=1e7+5;
int fa[maxn];
int find(int x){
	return x==fa[x]?x:(fa[x]=find(fa[x]));
} 

ll mpow(ll x,ll n,ll mod){//x是底數 n是指數 mod是模數 
	ll ans=1; 
	while(n){
		if(n&1) ans=ans*x%mod;
		x=x*x%mod; 
		n=n>>1;
	}
	return ans;
}

int main()
{
	int n,m;
	while(EOF!=scanf("%d%d",&n,&m)){
		for(int i=1;i<=n+1;i++) fa[i]=i;
		int cnt=n-m,l,r;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&l,&r);
			r++;
			l=find(l),r=find(r);
			if(l==r){
				cnt++;
				continue;
			}
			fa[l]=r;
		} 
		printf("%lld\n",mpow(26,cnt,mod));				
	}
	return 0;
}