摘要本文讲解如何为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若k0k0k0则输出接下来kkk个句子每行一个若k0k0k0则仅向前推进∣k∣|k|∣k∣个句子而不输出。当指针到达序列末尾时自动循环到开头。句子总数可能超过2632^{63}263但在__int128范围内。输入格式第一行为数据组数TTT。每组数据第一行一个正整数nnnn≤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原样输出。若k0k0k0则继续输出接下来kkk个句子每行一个。若k0k0k0则不输出句子。若k0k0k0只输出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可分解为ii0⋅(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}ii0⋅(L1L2⋯Lm−1)i1⋅(L2⋯Lm−1)⋯im−1即从高位到低位逐次带余除法。因此我们只需预计算每个节点的总长度及其辅助数组OR\texttt{OR}OR的前缀和、AND\texttt{AND}AND的后缀乘积即可在O(深度×出度)O(\text{深度} \times \text{出度})O(深度×出度)时间内生成任意句子。解题思路1. 建图与长度计算使用结构体存储节点类型、叶子字符、后继列表以及辅助数组prefixSumOR\texttt{OR}OR专用和suffixProdAND\texttt{AND}AND专用。记忆化递归计算len[u]叶子len[u] 1OR\texttt{OR}ORlen[u] sum(len[v])AND\texttt{AND}ANDlen[u] prod(len[v])由于题目保证结果在__int128范围内直接使用内置__int128类型避免手工实现大整数。2. 预处理辅助数组对于OR\texttt{OR}OR节点计算后继长度的前缀和prefixSum便于二分或顺序定位索引。对于AND\texttt{AND}AND节点计算从右向左的后缀乘积suffixProd其中suffixProd[i] L_{i1} * L_{i2} * ... * L_{m-1}。这样给定全局索引idx第iii个后继的局部索引为idx / suffixProd[i]然后idx % suffixProd[i]继续处理下一位。3. 递归生成句子函数generate(u, idx)返回节点u序列中索引为idx000-based的句子叶子返回其字符。OR\texttt{OR}OR在prefixSum中查找第一个大于idx的元素确定后继编号偏移量 idx - 前一个前缀和递归调用。AND\texttt{AND}AND依次对每个后继使用带余除法得到局部索引递归生成并拼接。4. 增量控制维护当前索引cur__int128类型总长度total len[0]。对于每个kkk输出k。若k0k0k0循环kkk次调用generate(0, cur)输出句子然后cur (cur 1) % total。若k0k0k0仅将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)。总生成次数所有k0k0k0的∣k∣|k|∣k∣之和不超过100×1000105100 \times 1000 10^5100×1000105完全可行。代码实现// Sentence Generator// UVa ID: 780// Verdict: Accepted// Submission Date: 2026-07-11// UVa Run Time: 0.030s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;usingBigInt__int128;enumNodeType{LEAF,OR,AND};structNode{NodeType type;charleafChar;vectorintsucc;vectorBigIntsuffixProd;vectorBigIntprefixSum;};vectorNodenodes;vectorBigIntlen;BigIntgetLength(intu){if(len[u]!-1)returnlen[u];if(nodes[u].typeLEAF)returnlen[u]1;BigInt res0;if(nodes[u].typeOR){for(intv:nodes[u].succ)resgetLength(v);}else{res1;for(intv:nodes[u].succ)res*getLength(v);}returnlen[u]res;}voidpreprocess(intu){if(nodes[u].typeOR){vectorBigIntpsnodes[u].prefixSum;ps.clear();BigInt acc0;for(intv:nodes[u].succ){accgetLength(v);ps.push_back(acc);}}elseif(nodes[u].typeAND){vectorBigIntspnodes[u].suffixProd;intm(int)nodes[u].succ.size();sp.resize(m);BigInt prod1;for(intim-1;i0;--i){sp[i]prod;prod*getLength(nodes[u].succ[i]);}}for(intv:nodes[u].succ)preprocess(v);}stringgenerate(intu,BigInt idx){if(nodes[u].typeLEAF)returnstring(1,nodes[u].leafChar);if(nodes[u].typeOR){constvectorBigIntpsnodes[u].prefixSum;for(inti0;i(int)ps.size();i){if(idxps[i]){BigInt offset(i0?idx:idx-ps[i-1]);returngenerate(nodes[u].succ[i],offset);}}}else{string res;BigInt curidx;constvectorBigIntspnodes[u].suffixProd;for(inti0;i(int)nodes[u].succ.size();i){BigInt idx_icur/sp[i];cur%sp[i];resgenerate(nodes[u].succ[i],idx_i);}returnres;}return;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;nodes.assign(n,Node());len.assign(n,-1);for(inti0;in;i){intid;string mark;cinidmark;if(mark*||mark|){intnumSucc;cinnumSucc;nodes[id].succ.resize(numSucc);for(intj0;jnumSucc;j)cinnodes[id].succ[j];nodes[id].type(mark*?AND:OR);nodes[id].leafChar0;}else{nodes[id].typeLEAF;nodes[id].leafCharmark[0];nodes[id].succ.clear();}}for(inti0;in;i)getLength(i);preprocess(0);BigInt cur0;BigInt totallen[0];intk;while(cink){coutk\n;if(k0)break;intcntabs(k);if(k0){for(inti0;icnt;i){coutgenerate(0,cur)\n;BigInt nxtcur1;cur(nxttotal?0:nxt);}}else{for(inti0;icnt;i){BigInt nxtcur1;cur(nxttotal?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)索引分解。递归生成句子深度可控。此方法避免了枚举所有组合适用于句子总数巨大的场景是处理组合爆炸问题的经典思路。
