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;
}
|