题目描述

Koishi决定走出幻想乡成为数学大师！ Flandre听说她数学学的很好，就给Koishi出了这样一道构造题： Task1：试判断能否构造并构造一个长度为n的的排列，满足其n个前缀和在模n的意义下互不相同 Taks2：试判断能否构造并构造一个长度为n的的排列，满足其n个前缀积在模n的意义下互不相同 按照套路，Koishi假装自己根本不会捉，就来找你帮忙辣。

问题一

容易知道n为大于1的奇数无解。
因为此时和为n的倍数所以第n项必须放n。
而不在第一项放n会使得存在两项相同，从而判断无解。
n为1特判掉。
考虑n为偶数如何构造。
可以考虑构造前缀和数组再倒推。
前缀和数组是0 1 n-1 2 n-2 3 n-3……n/2
容易证明减出来互不相同，这里略去。

问题二

容易知道n为大于4的合数无解。
因为n!肯定是n的倍数所以第n项必须放n。
假如n为合数能拆出n=pq
当p小于q时，显然(n-1)!含有p与q模n会为0。
当p等于q时，如果n大于4，就有2q<n，(n-1)!会含有至少两个q因此模n为0。
n等于4和1特判掉，然后考虑n为质数如何构造。
可以考虑构造前缀积数组再倒推。
前缀积数组是1 2 3 4 5 6……n
容易证明除出来互不相同，这里略去。 #include #include #include #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; const int maxn=100000+10; int a[maxn],b[maxn]; int i,j,k,l,t,n,m,ca,czy; int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; } void solve1(){ while (ca--){ n=read(); if (n%2==1){ if (n==1) printf("2 1 "); else printf("0 "); continue; } b[1]=0; fo(i,1,n/2){ b[i*2]=i; b[i*2+1]=n-i; } a[1]=n; fo(i,2,n) a[i]=((b[i]-b[i-1])%n+n)%n; printf("2 "); fo(i,1,n) printf("%d ",a[i]); printf(" "); } } int quicksortmi(int x,int y){ if (!y) return 1; int t=quicksortmi(x,y/2); t=(ll)t*t%n; if (y%2) t=(ll)t*x%n; return t; } bool pd(int n){ int i; fo(i,2,floor(sqrt(n))) if (n%i==0) return 1; return 0; } void solve2(){ while (ca--){ n=read(); if (n==1) printf("2 1 "); else if (n==2) printf("2 1 2 "); else if (n==4) printf("2 1 3 2 4 "); else{ if (pd(n)) printf("0 "); else{ a[1]=1; fo(i,2,n-1) a[i]=(ll)(i-1)*quicksortmi(i,n-2)%n; a[n]=n; printf("2 "); fo(i,1,n) printf("%d ",a[i]); printf(" "); } } } } int main(){ czy=read();ca=read(); if (czy==1) solve1(); else solve2(); }