P16928 Magic-Gathering Stones.

:::info[Background] When the mountain wind blew down from the northern ridge, it already carried ore dust and a chill. The path leading to the foot of the mountain was not wide. On both sides grew low gray-green shrubs, with leaf edges bitten pale by autumn frost. The distant sky was so clear it was almost transparent. A few black-feathered birds circled close to the cliff, occasionally letting out short cries, only to be quickly swallowed by the sound of the wind. Frieren walked in front. Her long staff lightly tapped the rocky ground, and the hem of her cloak swayed slowly with her steps. To her, such a road was not long. Even the growing chill in the wind year after year was only the seasons repeating themselves. “A little further ahead is Rozema Mining Town.” She looked at the few wisps of gray-white smoke rising in the distance, speaking as calmly as if stating something completely ordinary. Fern raised her head and saw a patch of dark brown rooftops set among the mountains. The town was built along the slope: stone walls, furnace towers, rail carts carrying ore, and furnaces that never went out, dyeing the whole town in a steady iron color. Even from a distance, the echoes of metal hammering could be faintly heard—once, again—like some slow and stubborn heartbeat. “Is that the place famous for magic-gathering stones?” Fern asked. “Yes.” Frieren nodded. “The veins around here are special. Only the ore from here can be polished into stable enough magic-gathering stones. They can store mana, and they also make spells more complete when released. For people going to dangerous places, they are quite handy.” “Sounds expensive…” Stark adjusted the pack on his back, showing a slightly complicated expression. “Do we really need to buy a lot?” Frieren stopped and looked back at him. “Yes, we do.” She said. “Because the place we are going next is the ‘Sunken Star Archive’.” Right then, the wind passed through the valley, pressing the dead grass by the roadside down together. Fern fell silent for a moment. She had heard Frieren mention that name several times—the ancient maze buried deeper in the mountains, said to have been built by some royal court archmage to seal away forbidden spellbooks. Later, the kingdom fell and the guards disappeared, leaving only layered corridors, lost spell formulas, and mana echoes that still had not faded away. Even after a long time, adventurers still kept vanishing there. “Is it… dangerous inside?” Stark asked softly. “Yes, very dangerous.” Frieren answered plainly. “Probably more troublesome than you think.” When she said that, her expression did not change, as if she were only commenting that today’s wind was colder than yesterday’s. Yet because of that, Fern could feel the danger of the maze even more. When Frieren described something as “troublesome” in such a flat tone, it was usually not something that could be solved easily. The downhill road gradually became gentler, and the outline of the mining town grew clearer bit by bit. The streets were paved with rough black stone, with deep and shallow ruts pressed into them. Thick dustproof cloth hung on window frames. Unsorted ore was piled in front of doors, giving off a dim, cold, hard shine. Craftsmen wearing leather aprons walked past the furnaces, and fine metal powder flicked up from their boot soles. The air was mixed with the smell of coal fire, ore sand, and hot iron, heavy on the body, making one think of those things buried deep underground, pressed by time for hundreds or thousands of years. Frieren stood at the town entrance and watched the busy little town for a while. “How rare,” she said softly. “Compared with fifty years ago, it hasn’t really changed much.” “Isn’t that normal?” Stark was startled. Fern did not speak, only stealing a glance at Frieren. For humans, fifty years is enough for children to grow up, for shops to change owners, for a whole street to replace every signboard. But for the elf before them, who had lived through a long time, that might really have been only a not-very-long separation. “Let’s go buy the magic-gathering stones first.” Fern brought the topic back. “Since only here can we buy them, we should prepare enough before entering the maze.” “Yes.” Frieren started walking. Her silver hair brushed lightly in the wind. “In the ‘Sunken Star Archive’, many things like to swallow other people’s mana. When the time comes, being able to cast spells steadily will be much more convenient.” “It really feels like you’re saying it so easily…” Stark sighed, but still followed. At that moment, the town bell rang, low and long, startling gray-feathered sparrows on the eaves. The three figures crossed the streets darkened by coal smoke and headed toward the old shop said to sell magic-gathering stones. Deep inside the doorway, the furnace fire flickered, like some kind of omen that would never go out. And the journey toward the maze began right here. ## 题目描述 . ## 输入格式 . ## 输出格式 . ## 提示 . --- :::info[Background] As dusk fell, the furnaces of Rozema Mining Town lit up one by one. Orange-red light reflected on the flagstone streets, and also on the neatly arranged surfaces of the magic-gathering stones on the counter. Those once quiet ores were now filled with mana, giving off a soft and steady glow, like clusters of starlight sealed inside stone. Fern carefully packed them into her bag. When her fingertips brushed the stone surface, she could still feel the warm mana slowly flowing within. Stark checked the ropes, rations, and weapons, fastened the last piece of gear, and let out a long breath. Frieren simply stood quietly outside the door, looking up at the sky at the end of the mountains as it gradually darkened, her gaze as calm as if she had seen such departures countless times. “Ready?” she asked softly. “Yes.” Fern nodded. “We can set off anytime.” Stark also responded. The night wind passed through the woods outside the town, bringing the damp scent of grass and trees. The three said no more. After a brief silence, they walked slowly along the path leading north. Under the moonlight, tree shadows swayed and crossed. Deep in the forest was pitch-dark, as if quietly gathering up all sounds. And at the silent end of that darkness, the “Sunken Star Archive” was quietly waiting for their arrival.

Frieren’s group bought $n$ magic-gathering stones and lined them up in a row, numbered from $1$ to $n$. Each magic-gathering stone has a mana storage amount $p_i$ and an ease-of-storage value $w_i$, where $p$ is a permutation of $1\sim n$, and $w_i$ is a positive integer. At the beginning, Frieren injected mana into the magic-gathering stone numbered $s$ and charged it. As mana continues to be injected, mana will gradually flow from the charged stones to adjacent uncharged stones. Specifically, suppose the magic-gathering stones with indices in $[l, r]$ have all been charged, then: - If $l = 1$, only the stone numbered $r+1$ will be charged. - If $r = n$, only the stone numbered $l-1$ will be charged. - Otherwise, the stone numbered $l - 1$ will be charged with probability $\frac{w_{l-1}}{w_{l-1} + w_{r+1}}$, and the stone numbered $r + 1$ will be charged with probability $\frac{w_{r+1}}{w_{l-1} + w_{r+1}}$. During one charging step, if the newly charged stone’s mana storage amount is strictly greater than the mana storage amounts of all previously charged stones, then a resonance occurs, making mana output smoother. Frieren wants to know: during this charging process, what is the expected number of resonances? Output the answer modulo $998244353$. **The initial charging at position $s$ is counted as one resonance.**

The first line contains two integers $n, s \ (1\leq s\leq n\leq 2\times 10^3)$, representing the number of magic-gathering stones and the index of the initially charged stone. The second line contains $n$ integers $p_1, p_2, ..., p_n \ (1\leq p_i\leq n)$, representing the mana storage amount of each magic-gathering stone. The data guarantees that $p$ is a permutation of $1\sim n$. The third line contains $n$ integers $w_1, w_2, ..., w_n \ (1\leq w_i\leq 10^9)$, representing the ease-of-storage value of each magic-gathering stone. The data guarantees that for any $i\neq j$, we have $w_i + w_j \not\equiv 0 \pmod{998244353}$.

Output one line containing one integer, representing the expected number of resonances, modulo $998244353$.

In modulo $p$ arithmetic, if there exists an integer $x$ such that $a\times x\equiv 1 \pmod{p}$, then $x$ is called the modular inverse of $a$ modulo $p$, written as $a^{-1}$. Therefore, for the rational number $\frac{a}{b}$, its value modulo $p$ is defined as $a\times b^{-1}$. Translated by ChatGPT 5