首页 > 代码库 > C 洛谷 P3599 Koishi Loves Construction [构造 打表观察]

C 洛谷 P3599 Koishi Loves Construction [构造 打表观察]

2024-09-02 19:28:26   217人阅读

题目描述

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

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

Task1：试判断能否构造并构造一个长度为技术分享的技术分享的排列，满足其技术分享个前缀和在模技术分享的意义下互不相同

Taks2：试判断能否构造并构造一个长度为技术分享的技术分享的排列，满足其技术分享个前缀积在模技术分享的意义下互不相同

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

输入输出格式

输入格式：

 

第一行两个整数技术分享和技术分享，分别表示Task类型和测试点内的数据组数。

接下来技术分享行，每行一个整数表示每组数据中的技术分享

 

输出格式：

 

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

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

  1. 如果您认为当前数据不存在符合题意的构造，只需输出一个整数技术分享

  2. 如果您认为当前数据存在符合题意的构造却不会构造，只需输出一个整数技术分享

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

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

 

输入输出样例

输入样例#1：
1 18
输出样例#1：
2 8 7 6 5 4 3 2 1
输入样例#2：
2 111
输出样例#2：
2 1 2 3 5 10 6 7 4 9 8 11

说明

对于每组数据

  1. 如果您对于构造的存在性判断正确，您将会得到技术分享的分数，若您的构造符合题意或者确实不存在符合题意的构造，您将会得到剩余的技术分享的分数。

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

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

测试点类型1：10分，满足技术分享

测试点类型2：40分，满足技术分享

测试点类型3：10分，满足技术分享

测试点类型4：40分，满足技术分享

对于所有测试点，满足技术分享

 

当时想出如何判断了但是不会构造

前缀和不存在就是n|(1+2+...+n)

前缀积不存在就是n|(n-1)!

直接上标解了：

 

Task1：

 

通过爆搜观察发现，除了 技术分享 以外的奇数都无解，偶数都有解。

 

证明：由于 技术分享 ，也就是说 技术分享 必须放于第一位，前缀和第一位一定是 技术分享 ，奇数情况下又由于 技术分享 ，也就是说前缀和最后一位一定是 技术分享 ，导致矛盾。

 

打表观察，每个偶数搜出来的方案都有 技术分享 ，不难证明其正确性。

 

Task2：

 

通过爆搜观察发现，除了 技术分享 以外的合数都无解，质数都有解。

 

证明：考虑到 技术分享 ，那么前缀积的最后一项一定是 技术分享 ，也就是说最后一项尽量放 技术分享 ，那么这要求 技术分享 ，发现只有 技术分享 和质数胜任这个要求。

 

打表观察，每个质数搜出来的前缀积方案都有 技术分享 ，也就是说第 技术分享 位就是 技术分享 ，通过逆元算出来就可以了。1和4的情况特判即可。

 

醉了快速幂又写成if(b)......

 

////  main.cpp//  CC////  Created by Candy on 2017/2/2.//  Copyright © 2017年 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}    return x*f;}int task,T,n;void solve1(int n){    if(n==1) puts("2 1");    else if(n&1) puts("0");    else{        printf("2 ");        printf("%d ",n);        for(int i=1;i<n;i++){            if(i&1) printf("%d ",i);            else printf("%d ",n-i);        }        puts("");    }}inline bool isP(int n){    if(n==2) return true;    int m=sqrt(n)+1;    for(int i=2;i<=m;i++) if(n%i==0) return false;    return true;}ll powMod(ll a,ll b,ll MOD){    ll ans=1;    for(;b;b>>=1,a=(a*a)%MOD)        if(b&1) ans=(ans*a)%MOD;    return ans;}void solve2(int n){    if(n==1) puts("2 1");    else if(n==2) puts("2 1 2");    else if(n==4) puts("2 1 3 2 4");    else if(!isP(n)) puts("0");    else{        printf("2 1 ");        for(int i=2;i<=n;i++){            printf("%lld ",(i*powMod(i-1,n-2,n)-1)%n+1);        }        puts("");    }}int main(int argc, const char * argv[]) {    task=read();T=read();    while(T--){        n=read();        if(task==1) solve1(n);        else solve2(n);    }    return 0;}

 

C 洛谷 P3599 Koishi Loves Construction [构造 打表观察]


联系
我们