LOJ #2014.
「SCOI2016」萌萌哒
题意
有一个没有前导零的 \(n\) 位十进制数
\(S_1 S_2\dotsc S_n\)，\(m\) 条限制，一条限制形如 \(S_{l_1}S_{l_1+1}\dotsc S_{r_2}\) 与 \(S_{l_2}S_{l_2+1}\dotsc S_{r_2}\)
这两个子串需要完全相同
问有多少种合法的方案
模 \(10^9+7\)
做法
考虑对应位连边，假设最后有 \(k\)
个联通块，方案数就是 \(9\times
10^{k-1}\)
连边数量是 \(\mathcal O(n^2)\)
的，考虑使用倍增优化连边
点 \(p_{i,j}\) 代表了以 \(j\) 为左端点，长度为 \(2^i\) 的区间，\(p_{i,j}\) 和 \(p_{i,k}\)
之间有边相当于对应的每个点之间有边
这样每个限制连边的数量是 \(\mathcal O(\log
n)\) 的
然后从大到小枚举 \(i\)，同一层的边可以用并查集去重，保留有效的至多
\(n-1\) 条边
一条 \(p_{i,j}\leftrightarrow
p_{i,k}\) 的边下传到第 \(i-1\)
层变成 \(p_{i-1,j}\leftrightarrow
p_{i-1,k}\) 和 \(p_{i-1,j+2^{i-1}}\leftrightarrow
p_{i-1,k+2^{i-1}}\) 的边
因此这种实现的总复杂度是 \(\mathcal
O(n\log^2 n)\) 的
可以轻易做到 \(\mathcal O(n\log n)\)
吧
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int N = 100005, P = 1000000007;
int n, m, f[N];
vector<pair<int,int>> ans, a[N];
int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}
int main() {
read(n), read(m);
while(m--){
static int l1, r1, l2, r2, len;
read(l1), read(r1), read(l2), read(r2), len=r1-l1+1;
for(int i=16; ~i; --i) if(len>>i&1)
a[i].push_back(make_pair(l1, l2)), l1+=1<<i, l2+=1<<i;
}
for(int i=1; i<=n; ++i) f[i]=i;
for(int i=16; ~i; --i){
for(auto j:a[i]) if(find(j.first)!=find(j.second))
f[f[j.first]]=f[j.second], ans.push_back(j);
if(i) for(auto j:ans)
a[i-1].push_back(j),
a[i-1].push_back(make_pair(j.first+(1<<i>>1), j.second+(1<<i>>1)));
}
int Ans=9;
for(int i=1; i<n-ans.size(); ++i) Ans=Ans*10ll%P;
return printf("%d", Ans), 0;
}
|