当前位置:网站首页>【luogu P3295】萌萌哒(并查集)(倍增)
【luogu P3295】萌萌哒(并查集)(倍增)
2022-07-05 23:34:00 【SSL_TJH】
萌萌哒
题目链接:luogu P3295
题目大意
给你一个大的数,然后有一些限制条件是如果把这个数看做一个串,有几对长度分别相同的子串是相同的。
然后问你有多少个数满足条件。
思路
可以发现基本跟数字没关系,就唯一的就是第一位不能是 0 0 0。
然后你会发现关系都是两个位置是同一个数,然后你考虑统计最后有多少数之间互不相关,如果是 n u m num num,那答案就是 9 ∗ 1 0 n u m − 1 9*10^{num-1} 9∗10num−1。
然后暴力一个一个合并是 n 2 n^2 n2 的,但是询问只是 n n n,我们考虑能不能中和一下。
先考虑怎么把操作变成 log n \log n logn,不难想到可以把它拆成 log n \log n logn 个区间,可以有倍增拆或者放到线段树上。
但是因为你是要一一对应的,你线段树上看起来就不太行了。
那我们考虑用倍增的方法拆,然后看看询问。
我们发现倍增的块内部我们弄并查集,它每个点是可以拆开乘两个的,但是也不能跟所有并查集里面的点拆开来的都连啊。
发现那样搞很冗余,我们考虑高效一点,观察到你并查集其实是用树的形式连接起来的,我们直接就跟父亲连边即可。
(就两边拆开两边分别连边)
然后就可以啦。
代码
#include<cstdio>
#define ll long long
#define mo 1000000007
using namespace std;
const int N = 1e5 + 100;
int n, m, fa[21][N];
ll ksm(ll x, ll y) {
ll re = 1; while (y) {
if (y & 1) re = re * x % mo; x = x * x % mo; y >>= 1;} return re;
}
int find(int now) {
return fa[(now - 1) / n][now - (now - 1) / n * n] == now ? now : fa[(now - 1) / n][now - (now - 1) / n * n] = find(fa[(now - 1) / n][now - (now - 1) / n * n]);}
void merge(int x, int y) {
int X = find(x), Y = find(y); if (X != Y) fa[(X - 1) / n][X - (X - 1) / n * n] = Y;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i <= 20; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++)
fa[i][j] = i * n + j;
for (int i = 1; i <= m; i++) {
int l1, r1, l2, r2; scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
for (int j = 20; j >= 0; j--)
if (l1 + (1 << j) - 1 <= r1) {
merge(j * n + l1, j * n + l2);
l1 = l1 + (1 << j); l2 = l2 + (1 << j);
}
}
for (int i = 20; i > 0; i--)
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
if (fa[i][j] != i * n + j) {
int fi = (fa[i][j] - 1) / n, fj = fa[i][j] - fi * n;
merge((i - 1) * n + j, (fi - 1) * n + fj);
merge((i - 1) * n + j + (1 << (i - 1)), (fi - 1) * n + fj + (1 << (fi - 1)));
}
}
int num = 0;
for (int i = 1; i <= n; i++) {
if (fa[0][i] == i) num++;
}
printf("%lld", 9ll * ksm(10, num - 1) % mo);
return 0;
}
边栏推荐
- C# 文件与文件夹操作
- TVS管和ESD管的技术指标和选型指南-嘉立创推荐
- In C#, why can't I modify the member of a value type instance in a foreach loop?
- What if the C disk is not enough? Let's see how I can clean up 25g of temp disk space after I haven't redone the system for 4 years?
- Go language introduction detailed tutorial (I): go language in the era
- The interface of grafana tool displays an error, incluxdb error
- Russian Foreign Ministry: Japan and South Korea's participation in the NATO summit affects security and stability in Asia
- 如何让同步/刷新的图标(el-icon-refresh)旋转起来
- Why use weak pointers for delegation- Why use weak pointer for delegation?
- PV静态创建和动态创建
猜你喜欢
GFS Distributed File System
Research notes I software engineering and calculation volume II (Chapter 1-7)
orgchart. JS organization chart, presenting structural data in an elegant way
成为程序员的你,后悔了吗?
Initialize your vector & initializer with a list_ List introduction
698. Divided into k equal subsets ●●
98. Verify the binary search tree ●●
TVS管 与 稳压二极管参数对比
PV静态创建和动态创建
GFS distributed file system
随机推荐
Initialiser votre vecteur & initialisateur avec une liste Introduction à la Liste
Golang code checking tool
Neural structured learning - Part 2: training with natural graphs
When to use useImperativeHandle, useLayoutEffect, and useDebugValue
Comparison of parameters between TVs tube and zener diode
5. Logistic regression
Common static methods of math class
The interface of grafana tool displays an error, incluxdb error
20220703 week race: number of people who know the secret - dynamic rules (problem solution)
11gR2 Database Services for &quot;Policy&quot; and &quot;Administrator&quot; Managed Databases (文件 I
哪些偏门项目可以做到?自媒体做到月赚一万以上很难吗?
Difference between out of band and in band
Pyqt control part (I)
How to enable relationship view in phpMyAdmin - how to enable relationship view in phpMyAdmin
424. The longest repeated character after replacement ●●
开源crm客户关系统管理系统源码,免费分享
Russian Foreign Ministry: Japan and South Korea's participation in the NATO summit affects security and stability in Asia
In C#, why can't I modify the member of a value type instance in a foreach loop?
【EF Core】EF Core与C# 数据类型映射关系
保研笔记二 软件工程与计算卷二(13-16章)