自动搬运

查看原文

来自洛谷，原作者为

	TemplateClass **

搬运于2025-08-24 22:31:35，当前版本为作者最后更新于2025-04-28 15:20:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\gdef \dp{\mathrm{dp}}$ $\gdef \son{\operatorname{son}}$ $\gdef \ssum{\operatorname{sum}}$

建图，对于两个有关联的循环（假设是第 $i$ 个和第 $j$ 个），我们连一条边 $(i, j)$；如果这个循环的上下界都是常数而非变量，朝结点 $0$ 连边。由于上下界最多只有一个变量，所以容易证明这是一个树。

然后我们开始 dp。设 $\dp _ {u, i}$ 表示第 $u$ 个循环的循环变量的值为 $i$ 时子树循环的次数，容易得到转移：

$$\dp _ {u, i} = \prod _ {v \in \son(u)} \sum _ {j = X _ v} ^ {Y _ v} \dp _ {v, j} $$

记 $V = 10 ^ 5$，直接按照这个式子转移是 $O(nV ^ 2)$ 的，时间复杂度显然承受不了，我们考虑用前缀和预处理后面那一坨和式，每次 $O(V)$ 地去维护即可，时间复杂度 $O(nV)$，然后就做完了。

#include<iostream>
#include<vector>
#include<utility>
#include<cctype>

#define x first
#define y second

constexpr int N = 26 + 5;
constexpr int V = 1e5 + 5;
constexpr int MOD = 1000000007;
typedef std::pair<int, int> Range;

int n; Range r[N]; std::vector<int> G[N];
int sum[N][V]; bool calc_ed[N];

inline int gsum(int u, int l, int r) {
	return l > r ? 0 : (sum[u][r] - sum[u][l - 1] + MOD) % MOD;
}

int solve_dp(int u, int i) {
	int ret = 1;
	for(const auto& v : G[u]) {
		if(!calc_ed[v] && (calc_ed[v] = true)) {
			int pL = r[v].x ? r[v].x : 1, pR = r[v].y ? r[v].y : V - 1;
			for(int j = pL; j <= pR; ++j) {
				sum[v][j] = (1ull * sum[v][j - 1] + solve_dp(v, j)) % MOD; 
			}
		}
		int L = (r[v].x ? r[v].x : i), R = (r[v].y ? r[v].y : i);
		ret = (1ull * ret * gsum(v, L, R)) % MOD;
	}
	return ret;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0), std::cout.tie(0);
	
	std::cin >> n;
	for(int i = 1; i <= n; ++i) {
		std::string a, b; std::cin >> a >> b;
		bool ia = std::isalpha(a[0]), ib = std::isalpha(b[0]);
		r[i].x = ia ? 0 : std::stoi(a), r[i].y = ib ? 0 : std::stoi(b);
		int ati = a[0] - 'a' + 1, bti = b[0] - 'a' + 1;
		G[ia ? ati : ib ? bti : 0].push_back(i);
	}
	std::cout << solve_dp(0, 0) << "\n";
	
	return 0;
}