{"problem":{"name":"[THUPC 2024 初赛] 分治乘法","description":{"content":"小艾想要挑战分治乘法。TA 将策略抽象成了如下问题： 现在给定一个目标集合 $T$，该集合是 $\\{1,\\dots,n\\}$ 的一个子集（$1\\leq n\\leq 5\\times 10^5$）。你需要通过一系列操作构造一些集合最后得到 $T$，具体来说有以下三种操作： - 创造一个大小为一的集合 $|S|=1$。 - 将已经被构造出的两个不交集合 $A, B$ 并起来，得到 $A\\cup B$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9969"},"statements":[{"statement_type":"Markdown","content":"小艾想要挑战分治乘法。TA 将策略抽象成了如下问题：\n\n现在给定一个目标集合 $T$，该集合是 $\\{1,\\dots,n\\}$ 的一个子集（$1\\leq n\\leq 5\\times 10^5$）。你需要通过一系列操作构造一些集合最后得到 $T$，具体来说有以下三种操作：\n\n- 创造一个大小为一的集合 $|S|=1$。\n- 将已经被构造出的两个不交集合 $A, B$ 并起来，得到 $A\\cup B$。\n- 将已经被构造出的一个集合 $A$ 进行平移，也即 $A+x = \\{ a+x : a\\in A \\}$。\n\n一个已经被构造出的集合可以在之后被使用多次。同时你需要保证操作过程中出现的所有集合都是 $\\{1,\\dots,n\\}$ 的子集。\n\n你的代价是构造出的所有集合的大小之和，你不需要最小化代价，只需要让代价控制不超过 $5\\times 10^6$ 即可。你用的操作数量也不应超过 $10^6$。\n\n## Input\n\n第一行输入一个正整数 $n$。\n\n接下来一行输入一个 `01` 串，长度为 $n$，第 $x$ 位为 `1` 表示 $x\\in T$，否则 $x\\notin T$，保证 $T$ 非空。\n\n## Output\n\n第一行输出一个正整数 $m$ 表示你使用的操作数量。\n\n接下来 $m$ 行，每行描述一个操作，设第 $i$ 次操作得到的集合为 $T_i$：\n\n- `1 x` 表示创造一个大小为一的集合 $\\{x\\}$。\n- `2 x y` 表示将不交集合 $T_x, T_y$ 并起来。\n- `3 x y` 表示将已经被构造出的一个集合进行平移，也即 $T_x+y$。\n\n你需要保证所有操作满足题目要求，并且最后一次操作产生的集合是 $T$。\n\n[samples]\n\n## Note\n\n### 样例 \\#1 解释\n\n- 第一次操作：创造集合 $T_1=\\{1\\}$。\n- 第二次操作：创造集合 $T_2=\\{4\\}$。\n- 第三次操作：将 $T_1, T_2$ 并起来，得到 $T_3=\\{1,4\\}$。\n- 第四次操作：将 $T_3$ 平移 $1$，得到 $T_4=\\{2,5\\}$。\n- 第五次操作：将 $T_3, T_4$ 并起来，得到 $T_5=\\{1,2,4,5\\}$。这就得到了 $T$。\n\n这个方案的总代价是 $1 + 1 + 2 + 2 + 4 = 10$。\n\n### 提示\n\n如果你的复杂度是好的，请相信常数。\n\n### 题目使用协议\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。\n\n以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）\n\n1. 任何单位或个人都可以免费使用或转载本仓库的题目；\n\n2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；\n\n3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9969","tags":["2024","Special Judge","THUPC"],"sample_group":[["5\n11011\n","5\n1 1\n1 4\n2 1 2\n3 3 1\n2 3 4\n"]],"created_at":"2026-03-03 11:09:25"}}