P3599 Koishi Loves Construction

    • 17通过
    • 154提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 数论,数学 洛谷原创 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Koishi决定走出幻想乡成为数学大师!

    Flandre听说她数学学的很好,就给Koishi出了这样一道构造题:

    Task1:试判断能否构造并构造一个长度为$n$ 的$1\dots n$ 的排列,满足其$n$ 个前缀和在模$n$ 的意义下互不相同

    Taks2:试判断能否构造并构造一个长度为$n$ 的$1\dots n$ 的排列,满足其$n$ 个前缀积在模$n$ 的意义下互不相同

    按照套路,Koishi假装自己根本不会捉,就来找你帮忙辣。

    输入输出格式

    输入格式:

    第一行两个整数$X$ 和$T$ ,分别表示Task类型和测试点内的数据组数。

    接下来$T$ 行,每行一个整数表示每组数据中的$n$

    输出格式:

    为了方便SPJ的编写,您需要遵从以下格式输出。

    对于每组数据仅包含一行输出:

    1. 如果您认为当前数据不存在符合题意的构造,只需输出一个整数$0$

    2. 如果您认为当前数据存在符合题意的构造却不会构造,只需输出一个整数$1$

    3. 如果您认为当前数据存在符合题意的构造并成功构造,则需要先输出一个整数$2$ ,再输出$n$ 个整数表示构造的方案。

    每两个整数之间需要有空格作为分隔符

    输入输出样例

    输入样例#1: 复制
    1 1
    8
    输出样例#1: 复制
    2 8 7 6 5 4 3 2 1
    输入样例#2: 复制
    2 1
    11
    输出样例#2: 复制
    2 1 2 3 5 10 6 7 4 9 8 11

    说明

    对于每组数据

    1. 如果您对于构造的存在性判断正确,您将会得到$30\%$ 的分数,若您的构造符合题意或者确实不存在符合题意的构造,您将会得到剩余的$70\%$ 的分数。

    2. 如果您对于构造的存在性判断不正确,您将不会得到任何分数。

    对于每组测试点,您的得分将是本组数据点中得分的最小值。

    测试点类型1:10分,满足$X=1,1\leq n\leq 10$

    测试点类型2:40分,满足$X=1,1\leq n\leq10^5$

    测试点类型3:10分,满足$X=2,1\leq n\leq 10$

    测试点类型4:40分,满足$X=2,1\leq n\leq10^5$

    对于所有测试点,满足$1\leq T\leq 10$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。