AtCoder WTF 2019 B Multiple of Nine/南外集训 2024.2.23 T1

给定 \(q\) 个区间 \(\{[l_i, r_i]\}\)，计算满足条件的长度为 \(n\) 的十进制数码串 \(S\) 的个数 \(\bmod 10^9+7\)：

• \(\forall i \in [1,q], num(S[l_i, r_i]) \equiv 0\pmod 9\)。

其中 \(num(T)\) 表示数码串 \(T\) 代表的整数，\(T[a, b]\) 表示子串 \(T_aT_{a+1}\dots T_b\)。在这道题中，我们允许任意形式的前导零。

\(1\le q\le 15, 1\le n\le 10^9\)。

所有涉及到的前缀和位置和 \(0\) 位置是关键位置，我们关心它们的前缀和 \(\bmod 9\) 的结果。假设我们已经知道了这些结果，且满足题中条件，考虑有多少种合法序列符合它。此时可以计算两个相邻的关键位置之间的位置的填法数：假设这两个位置间隔 \(d\)，则它们填出来的数有 \(\frac{10^d-1}{9}\) 种可能性 \(\bmod 9 = x\in[1,8]\)，而有 \(\frac{10^d-1}{9}+1\) 种可能性 \(\bmod 9 = 0\)。所以我们只关心这两个关键位置的前缀和 \(\bmod 9\) 是否相等。我们先用并查集合并题中给出的区间对应的关键位置，这样只剩下 \(\le q+1\) 个块，接下来再去处理这些块的可能的相等关系。

先计算出所有相邻关键位置前缀和都不同时的答案，然后计算出如果存在某个极大等价类，那么它会让答案乘以多少，这可以用 \(\Theta(q2^q)\) 得到。接下来使用相等关系容斥（实际上就是集合幂级数取 \(\ln\)），得到钦定一个等价类存在的权值，这一部分可以用某些集合幂级数技术做到 \(\Theta(q^22^q)\)，但是直接 \(\Theta(3^n)\) 也行。最后进行集合划分 DP，复杂度依然是 \(\Theta(q^22^q)\) 或 \(\Theta(3^q)\)。注意到我们似乎把 \(0\) 位置搞进来了，所以最后需要除以 \(9\)，表示 \(0\) 位置的这个连通块前缀和必须被钦定成 \(0\)。还要算上最后一段没被覆盖到的部分，这些位置显然可以任意填。

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int N = 16, MOD = 1000000007;

LL kpow(LL x, ULL k = MOD-2)
{
	x = x % MOD;
	LL r = 1;
	while (k)
	{
		if (k & 1) r = r * x % MOD;
		x = x * x % MOD;
		k >>= 1;
	}
	return r;
}

int len, n;
int a[N], b[N];
vector<int> pos;
int ff[N*2], co[N*2], tot_co;
LL tar[1 << N], coef[1 << N], f[1 << N];

int get_anc(int x)
{
	if (x == ff[x]) return x;
	return ff[x] = get_anc(ff[x]);
}

signed main(void)
{
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> len >> n;
	pos.assign(1, 0);
	F(i, 0, n-1) cin >> a[i] >> b[i], --a[i], pos.push_back(a[i]), pos.push_back(b[i]);
	sort(pos.begin(), pos.end());
	pos.erase(unique(pos.begin(), pos.end()), pos.end());
	F(i, 0, n-1)
	{
		a[i] = lower_bound(pos.begin(), pos.end(), a[i]) - pos.begin();
		b[i] = lower_bound(pos.begin(), pos.end(), b[i]) - pos.begin();
	}
	F(i, 0, SZ(pos)) ff[i] = i;
	F(i, 0, n-1) ff[get_anc(b[i])] = get_anc(a[i]);
	F(i, 0, SZ(pos)) if (ff[i] == i) co[i] = tot_co++;
	F(i, 0, SZ(pos)) co[i] = co[get_anc(i)];
	assert(tot_co <= N);

	LL xx = 1;
	F(i, 1, SZ(pos))
	{
		int d = pos[i] - pos[i-1];
		LL x = (kpow(10, d) - 1) * kpow(9) % MOD;
		(xx *= x) %= MOD;
	}
	F(w, 1, (1<<tot_co)-1)
	{
		tar[w] = 1;
		F(i, 1, SZ(pos))
		{
			if (!((w >> co[i] & 1) && (w >> co[i-1] & 1))) continue;
			int d = pos[i] - pos[i-1];
			LL x = (kpow(10, d) - 1) * kpow(9) % MOD;
			(tar[w] *= kpow(x) * (x+1) % MOD) %= MOD;
		}
		// cerr << w << ' ' << tar[w] << '\n';
		coef[w] = tar[w];
		int u = __lg(w&-w);
		for (int ww = w^1<<u; ww; ww = (ww - 1) & (w^1<<u))
		{
			(coef[w] -= tar[ww] * coef[w^ww]) %= MOD;
			(f[w] += f[ww] * coef[w^ww] % MOD * 9) %= MOD;
		}
		(f[w] += coef[w] * 9) %= MOD;
	}
	LL ans = f[(1<<tot_co)-1] * xx % MOD * kpow(10, len - pos.back()) % MOD * kpow(9);
	cout << (ans % MOD + MOD) % MOD << '\n';
	
	return 0;
}