当前位置:网站首页>[Luogu p3295] mengmengda (parallel search) (double)
[Luogu p3295] mengmengda (parallel search) (double)
2022-07-05 23:49:00 【SSL_ TJH】
adorable
Topic link :luogu P3295
The main idea of the topic
Give you a big number , Then there are some restrictions if we treat this number as a string , Several pairs of substrings with the same length are the same .
Then ask how many numbers you have meet the conditions .
Ideas
It can be found that it has nothing to do with numbers , The only thing is that the first one cannot be 0 0 0.
Then you will find that both positions are the same number , Then you consider how many numbers are irrelevant , If it is n u m num num, The answer is 9 ∗ 1 0 n u m − 1 9*10^{num-1} 9∗10num−1.
Then violence merges one by one n 2 n^2 n2 Of , But the inquiry is just n n n, Let's consider whether we can neutralize .
First consider how to turn the operation into log n \log n logn, It's not difficult to think that it can be disassembled into log n \log n logn Intervals , You can multiply it or put it on the line segment tree .
But because you have to correspond one by one , You don't look very good on the tree .
Then we consider using the method of multiplication , Then look at the inquiry .
We find that we get and search the set inside the doubled block , Each point of it can be disassembled and multiplied by two , But it can't be connected with all the points in the search set .
I found it redundant , Let's think about efficiency , Observing you and looking up sets are actually connected in the form of trees , We can connect with our father directly .
( Take apart the two sides and connect the two sides separately )
Then you can .
Code
#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;
}
边栏推荐
- The use of El cascader and the solution of error reporting
- 跟着CTF-wiki学pwn——ret2libc1
- Senparc.Weixin.Sample.MP源码剖析
- Objective C message dispatch mechanism
- How to enable relationship view in phpMyAdmin - how to enable relationship view in phpMyAdmin
- How to insert data into MySQL database- How can I insert data into a MySQL database?
- 20220703 week race: number of people who know the secret - dynamic rules (problem solution)
- 哪些偏门项目可以做到?自媒体做到月赚一万以上很难吗?
- 14 MySQL-视图
- MySQL delete uniqueness constraint unique
猜你喜欢
20220703 week race: number of people who know the secret - dynamic rules (problem solution)
openssl-1.0.2k版本升级openssl-1.1.1p
【LeetCode】5. Valid palindrome
Brushless drive design -- on MOS drive circuit
The use of El cascader and the solution of error reporting
20220703 周赛:知道秘密的人数-动规(题解)
JVM details
Breadth first search open turntable lock
同事悄悄告诉我,飞书通知还能这样玩
开关电源Buck电路CCM及DCM工作模式
随机推荐
【LeetCode】5. Valid Palindrome·有效回文
用列錶初始化你的vector&&initializer_list簡介
Fiddler Everywhere 3.2.1 Crack
XML配置文件(DTD详细讲解)
Qt 一个简单的word文档编辑器
Cwaitabletimer timer, used to create timer object access
yate. conf
Open3D 点云随机添加噪声
[SQL] SQL expansion languages of mainstream databases (T-SQL, pl/sql, pl/pgsql)
5. Logistic regression
用列表初始化你的vector&&initializer_list简介
21. PWM application programming
How to get all the values stored in localstorage
Spreadjs 15.1 CN and spreadjs 15.1 en
Golang code checking tool
Use CAS instead of synchronized
TVS管 与 稳压二极管参数对比
Neural structured learning 4 antagonistic learning for image classification
Rsync remote synchronization
如何提升口才