博客

并查集题目，表示被题意折磨的好惨，百度了好几篇文章才看懂题目。

区间合并问题，初始化每个节点为一个区间，这样得到的所有解为26^n，之后每输入一个区间，如果该区间没出现过且没被之前的区间等效过，则可操作区间数目-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;
    }
}