摘要：本文讲解如何为AND-OR\texttt{AND-OR}AND-OR有向无环图实现增量句子生成器。核心思路是把OR\texttt{OR}OR节点的序列连接视为区间划分、把AND\texttt{AND}AND节点的笛卡尔积视为混合进制编码，通过预计算节点长度、OR\texttt{OR}OR前缀和与AND\texttt{AND}AND后缀乘积，在O(n⋅d)O(n \cdot d)O(n⋅d)时间内生成任意索引对应的句子，并用
__int128处理超过2632^{63}263的句子总数，避免枚举组合爆炸。
题目描述
给定一个AND-OR\texttt{AND-OR}AND-OR有向无环图，每个节点表示一个句子序列的生成规则。
叶子节点生成一个单字符句子（即该节点的标号字符）。
OR\texttt{OR}OR节点将其后继节点生成的句子序列按顺序连接（先第一个后继的全部句子，再第二个后继的全部句子，依此类推）。
AND\texttt{AND}AND节点将其后继节点生成的句子按字典序（复合索引升序）进行笛卡尔积式连接：若有mmm个后继，生成序列为所有可能组合(s0,s1,…,sm−1)(s_0, s_1, \ldots, s_{m-1})(s0,s1,…,sm−1)的拼接，且组合按索引(i0,i1,…,im−1)(i_0, i_1, \ldots, i_{m-1})(i0,i1,…,im−1)的字典序排列。
根节点（编号000）生成的句子序列即为该图所描述的语言。
要求实现一个增量生成器：维护当前索引指针，每次给定整数kkk（∣k∣≤1000|k| \le 1000∣k∣≤1000），若k>0k>0k>0则输出接下来kkk个句子（每行一个），若k<0k<0k<0则仅向前推进∣k∣|k|∣k∣个句子而不输出。当指针到达序列末尾时自动循环到开头。句子总数可能超过2632^{63}263，但在__int128范围内。
输入格式
第一行为数据组数TTT。
每组数据：
- 第一行一个正整数nnn（n≤50n \le 50n≤50），表示图的节点数。
- 接下来nnn行描述节点000到n−1n-1n−1，每行格式：
- 叶子节点：
节点编号 字符（字符不是*或|） - AND\texttt{AND}AND节点：
节点编号 * 后继个数 后继1 后继2 ... - OR\texttt{OR}OR节点：
节点编号 | 后继个数 后继1 后继2 ...
（题目原文中OR\texttt{OR}OR标记为'1'，但实际输入使用'|'，代码同时支持两者）。
每个节点最多101010个后继，句子最大长度为808080字符。
- 叶子节点：
- 此后每行一个整数kkk（∣k∣≤1000|k| \le 1000∣k∣≤1000），直到读入000表示该组数据结束。每组数据总指令数不超过100100100。
输出格式
对于每个kkk：
- 先输出一行
k（原样输出）。 - 若k>0k>0k>0，则继续输出接下来kkk个句子，每行一个。
- 若k<0k<0k<0，则不输出句子。
- 若k=0k=0k=0，只输出
0并结束该组数据。
样例
输入
1 4 0 * 2 1 3 1 | 2 2 3 2 a 3 b -1 3 0输出
-1 3 bb ab bb 0题目分析
本题的核心是根据图结构快速定位并生成任意索引对应的句子，同时支持指针递增与循环。
由于图的规模很小（n≤50n \le 50n≤50，出度≤10\le 10≤10），但句子总数可能极大，不能枚举生成，必须利用规则直接映射。
- 对于OR\texttt{OR}OR节点，其序列是多个后继序列的首尾连接，因此全局索引可通过检查落入哪个后继的区间来确定。
- 对于AND\texttt{AND}AND节点，其序列是多个后继序列的笛卡尔积，按复合索引字典序排列，这等价于一个混合进制数：若后继长度分别为L0,L1,…,Lm−1L_0, L_1, \dots, L_{m-1}L0,L1,…,Lm−1，则索引iii可分解为i=i0⋅(L1L2⋯Lm−1)+i1⋅(L2⋯Lm−1)+⋯+im−1i = i_0 \cdot (L_1 L_2 \cdots L_{m-1}) + i_1 \cdot (L_2 \cdots L_{m-1}) + \cdots + i_{m-1}i=i0⋅(L1L2⋯Lm−1)+i1⋅(L2⋯Lm−1)+⋯+im−1，即从高位到低位逐次带余除法。
因此，我们只需预计算每个节点的总长度及其辅助数组（OR\texttt{OR}OR的前缀和、AND\texttt{AND}AND的后缀乘积），即可在O(深度×出度)O(\text{深度} \times \text{出度})O(深度×出度)时间内生成任意句子。
解题思路
1. 建图与长度计算
使用结构体存储节点类型、叶子字符、后继列表，以及辅助数组prefixSum（OR\texttt{OR}OR专用）和suffixProd（AND\texttt{AND}AND专用）。
记忆化递归计算len[u]：
- 叶子：
len[u] = 1 - OR\texttt{OR}OR：
len[u] = sum(len[v]) - AND\texttt{AND}AND：
len[u] = prod(len[v])
由于题目保证结果在__int128范围内，直接使用内置__int128类型，避免手工实现大整数。
2. 预处理辅助数组
- 对于OR\texttt{OR}OR节点，计算后继长度的前缀和
prefixSum，便于二分（或顺序）定位索引。 - 对于AND\texttt{AND}AND节点，计算从右向左的后缀乘积
suffixProd，其中suffixProd[i] = L_{i+1} * L_{i+2} * ... * L_{m-1}。这样给定全局索引idx，第iii个后继的局部索引为idx / suffixProd[i]，然后idx %= suffixProd[i]继续处理下一位。
3. 递归生成句子
函数generate(u, idx)返回节点u序列中索引为idx（000-based）的句子：
- 叶子：返回其字符。
- OR\texttt{OR}OR：在
prefixSum中查找第一个大于idx的元素，确定后继编号，偏移量 =idx - 前一个前缀和，递归调用。 - AND\texttt{AND}AND：依次对每个后继使用带余除法得到局部索引，递归生成并拼接。
4. 增量控制
维护当前索引cur（__int128类型），总长度total = len[0]。
对于每个kkk：
- 输出
k。 - 若k>0k>0k>0，循环kkk次：调用
generate(0, cur)输出句子，然后cur = (cur + 1) % total。 - 若k<0k<0k<0，仅将
cur向前推进|k|次（即cur = (cur + |k|) % total），不输出。
复杂度分析
- 长度计算与预处理：遍历所有节点及后继，O(n⋅d)O(n \cdot d)O(n⋅d)，d≤10d \le 10d≤10。
- 单次生成：递归深度为最长路径（≤n\le n≤n），每层需遍历后继（≤d\le d≤d）或进行常数次除法，故O(n⋅d)O(n \cdot d)O(n⋅d)。
- 总生成次数：所有k>0k>0k>0的∣k∣|k|∣k∣之和不超过100×1000=105100 \times 1000 = 10^5100×1000=105，完全可行。
代码实现
// Sentence Generator// UVa ID: 780// Verdict: Accepted// Submission Date: 2026-07-11// UVa Run Time: 0.030s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;usingBigInt=__int128;enumNodeType{LEAF,OR,AND};structNode{NodeType type;charleafChar;vector<int>succ;vector<BigInt>suffixProd;vector<BigInt>prefixSum;};vector<Node>nodes;vector<BigInt>len;BigIntgetLength(intu){if(len[u]!=-1)returnlen[u];if(nodes[u].type==LEAF)returnlen[u]=1;BigInt res=0;if(nodes[u].type==OR){for(intv:nodes[u].succ)res+=getLength(v);}else{res=1;for(intv:nodes[u].succ)res*=getLength(v);}returnlen[u]=res;}voidpreprocess(intu){if(nodes[u].type==OR){vector<BigInt>&ps=nodes[u].prefixSum;ps.clear();BigInt acc=0;for(intv:nodes[u].succ){acc+=getLength(v);ps.push_back(acc);}}elseif(nodes[u].type==AND){vector<BigInt>&sp=nodes[u].suffixProd;intm=(int)nodes[u].succ.size();sp.resize(m);BigInt prod=1;for(inti=m-1;i>=0;--i){sp[i]=prod;prod*=getLength(nodes[u].succ[i]);}}for(intv:nodes[u].succ)preprocess(v);}stringgenerate(intu,BigInt idx){if(nodes[u].type==LEAF)returnstring(1,nodes[u].leafChar);if(nodes[u].type==OR){constvector<BigInt>&ps=nodes[u].prefixSum;for(inti=0;i<(int)ps.size();++i){if(idx<ps[i]){BigInt offset=(i==0?idx:idx-ps[i-1]);returngenerate(nodes[u].succ[i],offset);}}}else{string res;BigInt cur=idx;constvector<BigInt>&sp=nodes[u].suffixProd;for(inti=0;i<(int)nodes[u].succ.size();++i){BigInt idx_i=cur/sp[i];cur%=sp[i];res+=generate(nodes[u].succ[i],idx_i);}returnres;}return"";}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;nodes.assign(n,Node());len.assign(n,-1);for(inti=0;i<n;++i){intid;string mark;cin>>id>>mark;if(mark=="*"||mark=="|"){intnumSucc;cin>>numSucc;nodes[id].succ.resize(numSucc);for(intj=0;j<numSucc;++j)cin>>nodes[id].succ[j];nodes[id].type=(mark=="*"?AND:OR);nodes[id].leafChar=0;}else{nodes[id].type=LEAF;nodes[id].leafChar=mark[0];nodes[id].succ.clear();}}for(inti=0;i<n;++i)getLength(i);preprocess(0);BigInt cur=0;BigInt total=len[0];intk;while(cin>>k){cout<<k<<"\n";if(k==0)break;intcnt=abs(k);if(k>0){for(inti=0;i<cnt;++i){cout<<generate(0,cur)<<"\n";BigInt nxt=cur+1;cur=(nxt==total?0:nxt);}}else{for(inti=0;i<cnt;++i){BigInt nxt=cur+1;cur=(nxt==total?0:nxt);}}}}return0;}总结
本题通过索引映射将AND-OR\texttt{AND-OR}AND-OR图的生成序列转化为混合进制编码，从而支持快速随机访问与增量遍历。
关键技巧：
- 利用
__int128简化大整数运算，在数据范围内高效且简洁。 - 预计算OR\texttt{OR}OR前缀和与AND\texttt{AND}AND后缀乘积，实现O(1)O(1)O(1)索引分解。
- 递归生成句子，深度可控。
此方法避免了枚举所有组合，适用于句子总数巨大的场景，是处理组合爆炸问题的经典思路。
)
