#P11978. [2023年联测]笋横着横笋

    ID: 11128 传统题 1000ms 512MiB 尝试: 5 已通过: 1 难度: 10 上传者: 标签>数论多项式与生成函数FFT字符串ManacherCF3100数学构造多项式生成函数

[2023年联测]笋横着横笋

笋横着横笋(ntt)

【题目描述】

这是一道「笋」模板题。

「笋」是一个喜欢骰子的「笋」,同时她也追求公平,于是在本题中,对于任意骰子,投掷后最终每一面朝上的概率相等。

「笋」有两个骰子,第一个有nn面,每一面上分别有 1∼n1\sim n;第二个有mm 面,每一面上分别有1∼m1\sim m。

「笋」厌倦了每天投这两个骰子,于是你需要帮「笋」构造两个骰子,它们的面数可以为任意正整数,且每一面上的数值也可以为任意正整数,并且可以重复,但是需要满足:

• 至少有一个骰子和原来的不同,两个骰子不同当且仅当存在正整数xx使得xx在两个骰子上的出现次数不同;

• 同时投掷两个骰子时,和的概率分布和原来一样,即对于任意正整数xx,同时投两个骰子得到的和为xx 的概率和原来一致。

在此基础上,你需要最小化两个骰子的面数之和。可以证明,在本题的限制下必然存在至少一组解。

【输入格式】

从标准输入读入。

本题单个测试点内有多组数据。第一行一个正整数tt表示数据组数。 对于每组数据,仅一行两个正整数表示n,mn,m。

【输出格式】

输出到标准输出。

对于每组数据,第一行输出两个正整数p,qp,q表示你构造的两个骰子的面数;第二行pp 个正整数表示你构造的第一个骰子每个面上的数;第三行qq个正整数表示你构造的第二个骰子每个面上的数。

为了防止你的输出过多把 checker 卡爆,因此你构造的p,qp,q需满足p+q≤2(n+m)p+q\le 2(n+m), 保证必然存在一组解满足该条件。

【样例 1 输入】

5
3 4
9 1
9 2
8 2
7 2

【样例 1 输出】

2 6
2 1
3 4 1 2 5 3
3 3
7 1 4
2 3 1
6 3
1 7 4 8 5 2
1 3 2
4 4
1 3 4 2
6 2 1 5
4 7
1 2 2 1
7 6 1 4 2 5 3

【提示】

本题下发文件中 checker.cpp 可以用来检验你的输出的正确性。使用时,请先编译 checker.cpp 得到可执行文件,然后运行如下命令:

• Windows: checker.exe <in> <out> <ans>
• Linux:./checker <in> <out> <ans>

其中 <in>、<out> 和 <ans> 分别表示输入文件名、你的输出文件名和答案文件名。 下发样例答案文件中,只包含了p+qp+q的最小值,没有包含具体方案。

若输出 Accepted 表示你的答案正确,否则表示答案错误,并会给出错在第几组数据。

【数据范围】

对于所有数据,满足$1\le t\le 10^{3},1\le n,m\le10^6,\ \sum\max(n,m)\le10^6$。

子任务编号 n,m≤n,m\le ∑max⁡(n,m)≤\sum\max(n,m)\le 分值 子任务依赖
1 1010 100100 1010
2 100100 15 1
3 10001000 1515 1,21,2
44 10410^{4} 2020 1,2,31,2,3
55 10510^{5} 1,2,3,41,2,3,4
66 10610^{6} 1,2,3,4,51,2,3,4,5