2014
03-30

# Code Lock

A lock you use has a code system to be opened instead of a key. The lock contains a sequence of wheels. Each wheel has the 26 letters of the English alphabet ‘a’ through ‘z’, in order. If you move a wheel up, the letter it shows changes to the next letter in the English alphabet (if it was showing the last letter ‘z’, then it changes to ‘a’).
At each operation, you are only allowed to move some specific subsequence of contiguous wheels up. This has the same effect of moving each of the wheels up within the subsequence.
If a lock can change to another after a sequence of operations, we regard them as same lock. Find out how many different locks exist?

There are several test cases in the input.

Each test case begin with two integers N (1<=N<=10000000) and M (0<=M<=1000) indicating the length of the code system and the number of legal operations.
Then M lines follows. Each line contains two integer L and R (1<=L<=R<=N), means an interval [L, R], each time you can choose one interval, move all of the wheels in this interval up.

The input terminates by end of file marker.

There are several test cases in the input.

Each test case begin with two integers N (1<=N<=10000000) and M (0<=M<=1000) indicating the length of the code system and the number of legal operations.
Then M lines follows. Each line contains two integer L and R (1<=L<=R<=N), means an interval [L, R], each time you can choose one interval, move all of the wheels in this interval up.

The input terminates by end of file marker.

1 1
1 1
2 1
1 2

1
26

#include <iostream>
#include <cstring>

using namespace std;

int father[10000001];
long long int ans;
int n,m;
const int mod=1000000007;
long long s;

int find(int x)
{
while (x!=father[x])
x=father[x];
return x;
}

void Union(int a,int b)
{
a=find(a);
b=find(b);
if (a==b)
return ;
father[a]=b;
ans--;
}

void init()
{
for (int i=0;i<=n;i++)
father[i]=i;
}

void fast_power()
{
s=1;
long long int t=26;
while (ans>0)
{
if (ans%2==1)
s=(s*t)%mod;
t=(t*t)%mod;
ans=ans/2;
}
}

int main()
{
while (cin>>n>>m)
{
int a,b;
init();
ans=n;
for (int i=1;i<=m;i++)
{
cin>>a>>b;
Union(a-1,b);
}
fast_power();
cout<<s<<endl;
}
}

1. 换句话说：想要灭亡人类统治世界，不花点银子哪能成？不舍得花银子都对不起“阴谋论”这个招牌！这帮G会不这么坏，怎么能显示出“阴谋论”的【伟光正】来…

2. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

3. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。