{"problem":{"name":"[JRKSJ R5] Concvssion","description":{"content":"给定长度为 $n$ 的序列 $a,b$，满足 $\\forall i\\in[1,n],a_i,b_i\\in[1,n]$。 定义一次操作为，$\\forall i\\in[1,n],b_i\\gets a_{b_i}$。 你需要依次进行 $n$ 次操作，每次操作后求出 $\\displaystyle\\sum_{i=1}^n b_i$ 对 $998244353$ 取模的答案。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8852"},"statements":[{"statement_type":"Markdown","content":"给定长度为 $n$ 的序列 $a,b$，满足 $\\forall i\\in[1,n],a_i,b_i\\in[1,n]$。\n\n定义一次操作为，$\\forall i\\in[1,n],b_i\\gets a_{b_i}$。\n\n你需要依次进行 $n$ 次操作，每次操作后求出 $\\displaystyle\\sum_{i=1}^n b_i$ 对 $998244353$ 取模的答案。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行 $n$ 个整数表示 $a_{1\\sim n}$。\n\n第三行 $n$ 个整数表示 $b_{1\\sim n}$。\n\n## Output\n\n共 $n$ 行，每行一个整数表示答案，答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/no6azjmn.png?x-oss-process=image)\n\n你很喜欢 Concvssion，但这并不妨碍你来做一道并不困难的有趣题目。\n\n（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）\n\n## Note\n\nIdea：cyffff，Solution：Ntokisq / WhisperingSnowflakes，Code：cyffff / WhisperingSnowflakes，Data：cyffff\n\n**Concvssion - Halv (Insane15.5)**\n### 数据规模\n本题采用捆绑测试。\n\n::cute-table\n| $\\text{Subtask}$ | $n\\le$ | 特殊性质 | $\\text{Score}$ |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $10^4$ | 无 | $10$ |\n| $2$ | $10^5$ | $\\forall i\\in[1,n],a_i\\le10^3$ | $10$ |\n| $3$ | ^ | $\\forall i\\in[1,n],a_i=i\\bmod n+1$ | $10$ |\n| $4$ | ^ | $a$ 是一个 $[1,n]$ 的排列 | $15$ |\n| $5$ | ^ | $a_1=1,\\forall i\\in[2,n],a_i< i$ | $25$ |\n| $6$ | ^ | 无 | $20$ |\n| $7$ | $3\\times10^5$ | ^ | $10$ |\n\n对于 $100\\%$ 的数据，$1\\le a_i,b_i\\le n\\le 3\\times10^5$。\n### 特殊评分方式\n本题开启子任务依赖，具体如下：\n- 对于子任务 $i\\in\\{1,2,3,5\\}$，您只需答对子任务 $i$ 即可获得子任务 $i$ 的分数。\n- 对于子任务 $i=4$，您需要答对所有 $j\\in[3,4]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。\n- 对于子任务 $i\\in\\{6,7\\}$，您需要答对所有 $j\\in[1,i]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8852","tags":["2022","多项式","洛谷原创","O2优化","树链剖分","生成函数","基环树","洛谷月赛"],"sample_group":[["5\n2 3 4 5 1\n2 2 3 1 1","14\n19\n19\n14\n9"],["5\n3 5 1 4 2\n2 2 3 1 1","17\n9\n17\n9\n17"],["5\n1 1 2 2 4\n2 2 3 1 1","6\n5\n5\n5\n5"],["5\n3 1 5 3 4\n2 2 1 3 3","15\n19\n20\n21\n19"]],"created_at":"2026-03-03 11:09:25"}}