黑大帅的灯会

\\n\\n## 题目背景\\n\\n2026 年的新年钟声即将敲响，银装素裹的长街上挂满了各式各样的红灯笼。\\n\\n作为新年庆典的总策划，黑大帅希望这场灯会能展现出一种独特的“数学美”。它不想让灯笼孤立地发光，而是设计了一种奇妙的传导机制：每一个灯笼燃烧产生的热量，不仅照亮自己，还会通过特殊的导管，单向传递给另一个特定的灯笼，汇聚成更耀眼的光芒。\\n\\n> “真正的年味，在于万家灯火的连接。”\\n\\n为了检验这套系统的稳定性，黑大帅记录了若干个关键位置灯笼的“总亮度”。现在，它想知道在总燃料有限的情况下，有多少种初始的点火方案，能够恰好达成眼前这般绚烂的景象。\\n\\n## 题目描述\\n\\n长街上共有 $n$ 盏灯笼，编号为 $1$ 到 $n$。每盏灯笼 $i$ 初始会装填 $a_{i}$ 单位的燃料（$a_{i}$ 为非负整数）。\\n\\n灯笼之间的能量传递遵循 **“二进制共鸣定律”**：定义函数 $g\\\\left(x\\\\right)$ 为 $x$ 在二进制表示下最低位的$1$ 所代表的数值（即 $x$ 的所有因子中最大的$2$ 的整数次幂）。例如：$g\\\\left(6\\\\right)=g\\\\left(110_{2}\\\\right)=2$， $g\\\\left(12\\\\right)=g\\\\left(1100_{2}\\\\right)=4$。\\n\\n能量传递规则如下：编号为 $i$ 的灯笼，会将自身产生的所有能量（包括初始燃料产生的能量，以及从其他灯笼接收到的能量）单向传递给编号为 $i+g\\\\left(i\\\\right)$ 的灯笼。如果 $i+g\\\\left(i\\\\right)>n$，则这部分能量会溢出长街，不再被任何灯笼接收（但仍计入总消耗）。\\n\\n我们定义灯笼 $u$ 的**最终亮度** $S_{u}$ 为：所有能通过传递路径流向 $u$ 的灯笼（含 $u$ 自身）的初始燃料 $a$ 之和。\\n\\n现在的已知信息如下：\\n\\n1. 所有 $n$ 盏灯笼的初始燃料之和 $\\\\sum_{i=1}^{n} a_{i}$ 恰好为 $K$。\\n2. 观测到了 $m$ 盏关键灯笼的最终亮度，即给出了 $m$ 对 $\\\\left(u_{j},w_{j}\\\\right)$，表示 $S_{u_{j}}=w_{j}$。\\n\\n请你计算，有多少种不同的初始燃料序列 $A=\\\\left[a_{1},a_{2},\\\\dots ,a_{n}\\\\right]$，满足上述所有条件？答案可能很大，请输出对 $998244353$ 取模的结果。若不存在任何满足条件的方案，输出 $0$。\\n\\n## 输入格式\\n\\n第一行包含三个整数 $n,m,K$，分别表示灯笼的数量、观测记录的数量、以及总燃料限制。\\n\\n接下来 $m$ 行，每行包含两个整数 $u,w$，表示观测到灯笼 $u$ 的最终亮度 $S_{u}$ 为 $w$。\\n\\n数据保证不会对同一个灯笼进行重复观测。\\n\\n## 输出格式\\n\\n输出一行一个整数，表示满足条件的方案数。\\n\\n```input1\\n5 1 10\\n4 6\\n```\\n\\n```output1\\n84\\n```\\n\\n## 数据范围\\n\\n对于 $10\\\\%$ 的测试数据，满足 $n\\\\le 10,K\\\\le 10$。\\n\\n对于另 $20\\\\%$ 的测试数据，满足 $n\\\\le 1000,K\\\\le 2000$。\\n\\n对于 $100\\\\%$ 的测试数据，满足 $1\\\\le n\\\\le 2\\\\times 10^{5}$，$1\\\\le m\\\\le n$，$0\\\\le K\\\\le 10^{18}$，$0\\\\le w\\\\le K$。\\n\

状态	递交者	时间	内存	语言	代码	递交时间
AC	rinsmq	393ms	6.7 MiB	C++20(O2)	2.9 KiB	2026-1-7 8:58:55
AC	Tobo	544ms	4.8 MiB	C++20(O2)	9.1 KiB	2025-12-31 9:50:39

统计

递交统计

黑大帅的灯会

信息

还没有账户？

登录