hdu 3461 Code Lock

http://acm.hdu.edu.cn/showproblem.php?pid=3461
パラレルセットとべき乗型取り
この問題は主に操作できない区間を求めている.

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 #include <iostream>

 5 #define maxn 10000010

 6 #define ll long long

 7 using namespace std;

 8 const int mod=1000000007;

 9 

10 int f[maxn];

11 int n,m;

12 int cnt=0;

13 

14 void inti()

15 {

16     for(int i=0; i<=n+1; i++)

17     {

18         f[i]=i;

19     }

20 }

21 

22 int find1(int x)

23 {

24     if(x==f[x]) return x;

25     return f[x]=find1(f[x]);

26 }

27 

28 void merge1(int a,int b)

29 {

30     int fa=find1(a);

31     int fb=find1(b);

32     if(fa!=fb)

33     {

34         f[fb]=fa;

35         cnt++;

36     }

37 }

38 

39 ll pow_mod(ll a,ll n)

40 {

41     if(n==0) return 1;

42     if(n==1) return a;

43     ll x=pow_mod(a,n/2);

44     ll ans=(ll)x*x%mod;

45     if(n%2==1) ans=ans*a%mod;

46     return ans;

47 }

48 

49 int main()

50 {

51     while(scanf("%d%d",&n,&m)!=EOF)

52     {

53         inti();

54         cnt=0;

55         for(int i=0; i<m; i++)

56         {

57             int l,r;

58             scanf("%d%d",&l,&r);

59             merge1(l,r+1);

60         }

61         cout<<pow_mod(26,n-cnt)<<endl;

62     }

63     return 0;

64 }

View Code