{"problem":{"name":"「Wdoi-2」禁断之门对面，是此世还是彼世","description":{"content":"给定一场长度为 $n$ 的正整数序列 $a$ 和一个长度为 $m$ 的正整数序列 $b$。 现在蓝根据序列 $a$ 与序列 $b$ 构造了一个 $n$ 行 $m$ 列的正整数矩阵 $A$ 满足 $A_{i,j}=a_ib_j$，你需要构造 $n+1$ 行 $t$ 列的正整数矩阵 $B$ 满足以下条件： - 矩阵的每个元素取值在 $[1,m]$ 间； - 矩阵同一行的元素**两两**不相同； -","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8544"},"statements":[{"statement_type":"Markdown","content":"给定一场长度为 $n$ 的正整数序列 $a$ 和一个长度为 $m$ 的正整数序列 $b$。\n\n现在蓝根据序列 $a$ 与序列 $b$ 构造了一个 $n$ 行 $m$ 列的正整数矩阵 $A$ 满足 $A_{i,j}=a_ib_j$，你需要构造 $n+1$ 行 $t$ 列的正整数矩阵 $B$ 满足以下条件：\n\n- 矩阵的每个元素取值在 $[1,m]$ 间；\n- 矩阵同一行的元素**两两**不相同；\n- 矩阵的每列**相邻元素**不同；\n- 在所有满足上面三项要求的矩阵中**最小化**下式：\n$$f(B)=\\sum\\limits_{i=1}^{n}\\sum\\limits_{j=1}^{t}\\sum\\limits_{k=\\min(B_{i,j},B_{i+1,j})}^{\\max(B_{i,j},B_{i+1,j})}A_{i,k}$$\n\n请输出构造出的 $B$ 矩阵的 $f(B)$ 的值模 $10^9+7$ 的结果。\n\n## Input\n\n第一行三个整数 $n,m,t$。\n\n接下来一行 $n$ 个整数 $a_1,a_2,\\cdots a_n$，含义如题面中所述。\n\n接下来一行 $m$ 个整数 $b_1,b_2,\\cdots b_m$，含义如题面中所述。\n\n## Output\n\n输出一行，表示构造出的 $B$ 矩阵的 $f(B)$ 的值模 $10^9+7$ 的结果。\n\n[samples]\n\n## Background\n\n或许是后户之国轻易不与外界联系，或许是神职所限，又或许是性格喜好的原因，摩多罗作为最初建立幻想乡的几位贤者之一，和其他贤者之间的联系并不频繁。其他如八云紫、茨木华扇等贤者均亲身走在幻想乡之中，而摩多罗却置身之外。\n\n耗费神力发动全幻想乡级别的异变，看似规模宏大，其实并未对幻想乡造成真正的伤害，只是让一群笨蛋妖精狂躁了些而已。 \n\n谁也不知道门后的秘神心中真正的想法。\n\n## Note\n\n### 样例解释 1\n\n根据题意，可以构造出矩阵 $A=\\begin{bmatrix}54 & 9 \\\\ 54 & 9 \\end{bmatrix}$。\n\n你需要构造出的 $3$ 行 $2$ 列的矩阵 $B=\\begin{bmatrix}1 & 2 \\\\ 2 & 1 \\\\ 1 & 2 \\end{bmatrix}$，此时 $f(B)=252$ 为最小值\n\n可以证明 $f(B)=252$ 为所有情况中，$f(B)$ 的最小值。\n\n### 数据范围及约定\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\bm{n \\le } & \\bm{m \\le } & \\bm{t \\le } & \\textbf{特殊性质} & \\textbf{分值}\\\\\\hline\n1 & 10 & 10 & 10 & - & 5 \\\\\\hline\n2 & 100 & 100 & 100 & - & 5 \\\\\\hline\n3 & 10^3 & 10^3 & 10^3 & - & 15 \\\\\\hline\n4 & 5\\times 10^4 & 5\\times 10^4 & 5\\times 10^4 & - & 30 \\\\\\hline\n5 & 5\\times 10^5 & 5\\times 10^5 & 5\\times 10^5 & \\textbf{A} & 10 \\\\\\hline\n6 & 5\\times 10^5 & 5\\times 10^5 & 5\\times 10^5 & \\textbf{B} & 10 \\\\\\hline\n7 & 5\\times 10^5 & 5\\times 10^5 & 5\\times 10^5 & - & 25 \\\\\\hline\n\\end{array}$$\n\n- **特殊性质** $\\textbf{A}$：保证 $a_i=1$；\n- **特殊性质** $\\textbf{B}$：保证 $m=t$。\n\n对于全部数据，保证 $1\\le a_i, b_i\\le 10^9$，$1\\le n, m, t\\le 5\\times 10^5 $，$t\\le m$。保证数据有解。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8544","tags":["动态规划 DP","二分","洛谷原创","O2优化","凸完全单调性（wqs 二分）","洛谷月赛"],"sample_group":[["2 2 2\n9 9\n6 1","252"],["10 10 10\n2 8 10 10 10 2 5 8 9 3\n2 1 5 2 10 7 8 9 10 6\n","8040\n"]],"created_at":"2026-03-03 11:09:25"}}