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