P7618 [COCI2011-2012#2] FUNKCIJA 题解

看起来比较复杂，但实际上是一个树上 dp 的模型。

因为每一重循环都最多有一个依赖，可以转化为树上的父子关系，于是就形成了一个森林。

对于非叶子节点，设 \(f_{u,i}\) 表示第 \(u\) 循环变量的值是 \(i\) 时所有直接或间接依赖于它的循环变量（即以它为根的子树除开它的部分）循环次数，对非根节点设 \(g_{u,i}\) 表示当第 \(u\) 个变量依赖的循环变量值为 \(i\) 时它和所有直接或间接依赖于它的循环变量（即以它为根的子树）循环次数。

对于非叶子节点，可以发现一个节点的子节点的子树是不互相影响的，也就是说交换子树之间循环的内外位置是不会影响答案的，根据乘法原理，\(f_{u,i}=\prod g_{v,i}\)，其中 \(v\) 是 \(u\) 的子节点。

对于非根节点，父亲节点循环变量的取值会限制这个变量的取值范围，所以 \(g\) 应该是 \(f\) 的一个区间和。具体地，如果父亲节点限制了取值的上界，则当 \(i<x_u\) 时，\(g_{u,i}=0\)，当 \(i\ge x_u\) 时，\(g_{u,i}=\sum_{j=x_u}^i f_{u,j}\)；如果父亲节点限制了取值的下界，则当 \(i>y_u\) 时，\(g_{u,i}=0\)，当 \(i\le y_u\) 时，\(g_{u,i}=\sum_{j=i}^{y_u}f_{u,i}\)，可以用前缀和优化。

对每棵树处理完 dp 数组之后，考虑计算答案。可以发现对于所有子树之间的循环内外关系也是可以交换的，所以答案就是所有根节点对答案贡献的乘积，如果根节点 \(u\) 有儿子节点，就让答案乘上 \(\sum_{i=x_u}^{y_u}f_{u,i}\)，如果没有儿子节点，那这就是一层没有限制也不限制其他变量取值的循环了，就让答案乘上 \(y_u-x_u+1\)。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 30, M = 1e5 + 5, P = 1e9 + 7;

int n, m = 1e5;
char str[N];
int x[N], y[N], fa[N], op[N];
int la[N], ne[N], en[N], idx;
bool st[N];
LL f[N][M], s[N][M];
LL res;

void add(int a, int b)
{
	ne[ ++ idx] = la[a];
	la[a] = idx;
	en[idx] = b;
}

void add(LL &x, LL y)
{
	x += y;
	if(x >= P) x -= P;
}

void dfs(int u)
{
	st[u] = true;
	if(!la[u])
	{
		if(op[u] == 1)
			for(int j = 1; j <= m; j ++ ) f[u][j] = max(y[u] - j + 1, 0);
		else
			for(int j = 1; j <= m; j ++ ) f[u][j] = max(j - x[u] + 1, 0);
		for(int j = 1; j <= m; j ++ ) s[u][j] = s[u][j - 1], add(s[u][j], f[u][j]);
	}
	else
	{
		for(int i = 1; i <= m; i ++ ) f[u][i] = 1;
		for(int i = la[u]; i; i = ne[i])
		{
			int v = en[i];
			dfs(v);
			for(int j = 1; j <= m; j ++ ) f[u][j] = f[u][j] * f[v][j] % P;
			for(int j = 1; j <= m; j ++ ) s[u][j] = s[u][j - 1], add(s[u][j], f[u][j]);
		}
		if(fa[u])
		{
			if(op[u] == 1)
				for(int j = 1; j <= m; j ++ )
				{
					if(j > y[u]) f[u][j] = 0;
					else f[u][j] = s[u][y[u]], add(f[u][j], P - s[u][j - 1]);
				}
			else
				for(int j = 1; j <= m; j ++ )
				{
					if(j < x[u]) f[u][j] = 0;
					else f[u][j] = s[u][j], add(f[u][j], P - s[u][x[u] - 1]);
				}
			for(int j = 1; j <= m; j ++ ) s[u][j] = s[u][j - 1], add(s[u][j], f[u][j]);
		}
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ )
	{
		scanf("%s", str);
		if(str[0] > '9')
		{
			fa[i] = str[0] - 'a' + 1;
			op[i] = 1;
			add(fa[i], i);
		}
		else
			for(int j = 0; str[j]; j ++ ) x[i] = x[i] * 10 + str[j] - 48;
		scanf("%s", str);
		if(str[0] > '9')
		{
			fa[i] = str[0] - 'a' + 1;
			op[i] = 2;
			add(fa[i], i);
		}
		else
			for(int j = 0; str[j]; j ++ ) y[i] = y[i] * 10 + str[j] - 48;
	}
	
	res = 1;
	for(int i = 1; i <= n; i ++ )
		if(!st[i])
		{
			if(la[i])
			{
				dfs(i);
				res = res * (s[i][y[i]] - s[i][x[i] - 1] + P) % P;
			}
			else res = res * (y[i] - x[i] + 1) % P;
		}
	
	printf("%lld\n", res);
	return 0;
}