描述
题解
英语渣渣表示,虽然看着别人的题解知道要求26^(n-count)
(count
是区间个数),但是依然无法理解题意,∑q|゚Д゚|p~~~
求这个区间个数很自然要用并查集,但是光这样还不够,因为n
比较大,所以需要用到快速幂来求最后的结果。
代码
#include <stdio.h>
const int MOD = 1e9 + 7;
const int MAXN = 1e7 + 10;
int pre[MAXN];
int count;
int find(int x)
{
int r = x;
while (r != pre[r])
{
r = pre[r];
}
int i = x;
while (i != r)
{
int j = pre[i];
pre[i] = r;
i = j;
}
return r;
}
void join(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
{
pre[fx] = fy;
count++;
}
}
long long power(int n)
{
long long sum = 1, tmp = 26;
while (n)
{
if (n & 1)
{
sum = sum * tmp;
sum %= MOD;
}
tmp = (tmp * tmp) % MOD;
n >>= 1;
}
return sum;
}
int main()
{
int n, m, l, r;
while (scanf("%d%d", &n, &m) != EOF)
{
count = 0;
for (int i = 0; i <= n; i++)
{
pre[i] = i;
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &l, &r);
join(l - 1, r);
}
printf("%lld\n", power(n - count) % MOD);
}
return 0;
}