模拟赛看了一眼题太史了跳了，结果这题怎么这么简单？

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,P=1e9+7;
int dp[50][N],s[50][N],l[50],r[50],op[50],v[50];vector<int>G[50];
void dfs(int x)
{
	v[x]=1;for(int i=1;i<=N-10;i++)dp[x][i]=-1;
	if(G[x].empty())
		for(int i=1;i<=N-10;i++)dp[x][i]=1;
	for(int y:G[x])
	{
		dfs(y);
		for(int i=1;i<=N-10;i++)
		{
			if(op[y]==1)
			{
				if(i>r[y]){dp[x][i]=0;continue;}
				if(dp[x][i]==-1)dp[x][i]=1;
				dp[x][i]=dp[x][i]*((s[y][r[y]]-s[y][i-1])%P+P)%P;
			}
			else
			{
				if(i<l[y]){dp[x][i]=0;continue;}
				if(dp[x][i]==-1)dp[x][i]=1;
				dp[x][i]=dp[x][i]*((s[y][i]-s[y][l[y]-1])%P+P)%P;
			}
		}
	}
	for(int i=1;i<=N-10;i++)if(dp[x][i]==-1)dp[x][i]=0;
	for(int i=1;i<=N-10;i++)s[x][i]=(s[x][i-1]+dp[x][i])%P;
}
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s1,s2;cin>>s1>>s2;
		if('a'<=s1[0]&&s1[0]<='z')
		{
			int t=s1[0]-'a'+1;op[i]+=1;
			G[t].push_back(i);
		}
		else for(int j=0;j<s1.size();j++)
			l[i]=l[i]*10+(s1[j]-'0');
		if('a'<=s2[0]&&s2[0]<='z')
		{
			int t=s2[0]-'a'+1;op[i]+=2;
			G[t].push_back(i);
		}
		else for(int j=0;j<s2.size();j++)
			r[i]=r[i]*10+(s2[j]-'0');
	}
	for(int i=1;i<=n;i++)if(!v[i])dfs(i);
	int ans=1;
	for(int i=1;i<=n;i++)if(op[i]==0)ans=ans*((s[i][r[i]]-s[i][l[i]-1])%P+P)%P;
	cout<<ans;
	return 0;
}

Problem

$n$ 个嵌套 for 循环，对每个循环变量给出上下界（数或至多一个外层的变量），求最内层的循环次数。

Solution

通过日常代码经验，交换两个毫无关联（没有直接或间接关联）的循环对整体次数没有影响，所以，我们考虑对每一坨关联起来的循环分开计算。

对于一坨循环，通过它们的关联关系，把它们画成一棵树，表示其依赖关系。

然后，掏出树形 DP，$f_{u,i}$ 表示循环 $u$ 的循环变量为 $i$ 时其子树的总循环次数，对于 $u$ 的每个儿子 $v_k$，它们的先后是随意的。所以，为了便于理解，假设先进行 $v_1$ 的所有循环，再进行 $v_2,v_3,\cdots,v_k$ 的循环。设当儿子的循环变量取 $l$ 时可以转移到当前节点，于是可以得到（分步乘起来）:

只剩最后一个问题，儿子中有哪些 $l$ 可以转移过来。这是比较容易的，对于一个已经确定的循环变量 $i$，可以根据上下界的定义，直接 for 模拟一遍。

简单计算一下时间复杂度为 $O(n\times10^{10})$（$n$ 个循环，一个循环值域为 $10^5$，再枚举一遍儿子节点的值域 $10^5$）。明显是不行的。

再研究一下，显而易见地发现，儿子中可转移的东西是连续的（毕竟是 ++i）,于是就拿出前缀和优化，砍掉一个 $10^5$。

最后，在算完每一坨之后，因为是嵌套的循环，就把每一坨的循环次数乘起来得出答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N(30),M(1e5+10),mod(1e9+7);
int n,a[N],b[N],d[N],h[N],ne[N],e[N],idx;
ll f[N][M],ans=1,sum[N][M];
bool fg[N];
inline ll mo(ll x){
	return x<mod?x:x-mod;
}
inline void add(int u,int v){
	ne[++idx]=h[u],h[u]=idx,e[idx]=v;
}
inline void dfs(int u){
	for(int i=a[u];i<=b[u];++i) f[u][i]=1;
	for(int i=h[u];i;i=ne[i]){
		int v=e[i];
		dfs(v);
		for(int j=a[u];j<=b[u];++j){
			if(d[v]) f[u][j]=f[u][j]*(a[v]<=j?sum[v][j]-sum[v][a[v]-1]+mod:0)%mod;
			else f[u][j]=f[u][j]*(j<=b[v]?sum[v][b[v]]-sum[v][j-1]+mod:0)%mod;
		}
	}
	for(int i=a[u];i<=b[u];++i) sum[u][i]=mo(sum[u][i-1]+f[u][i]);
}
int main(){
	string l,r;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		a[i]=1,b[i]=M-1;
		cin>>l>>r;
		int ff=0;
		if(l[0]>='a'&&l[0]<='z') add(l[0]-'a'+1,i);
		else{
			a[i]=0;
			for(int j=0;j<l.size();++j) a[i]=(a[i]<<1)+(a[i]<<3)+(l[j]-'0');
			++ff;
		}
		if(r[0]>='a'&&r[0]<='z') add(r[0]-'a'+1,i),d[i]=1;
		else{
			b[i]=0;
			for(int j=0;j<r.size();++j) b[i]=(b[i]<<1)+(b[i]<<3)+(r[j]-'0');
			++ff;
		}
		if(ff==2) fg[i]=1;
	}
	for(int i=1;i<=n;++i)
		if(fg[i]) dfs(i),ans=ans*(sum[i][b[i]]-sum[i][a[i]-1]+mod)%mod;
	printf("%lld",ans);
	return 0;
}