【题解】P3599 Koishi Loves Construction
(mod n) 考虑如何构造,发现(n)一定在第一位,不然不行。(n)一定是偶数或者是(1),不然 (n|frac{n(n+1)}{2})则最后一项一定会和第一项相同。考虑让他们的前缀和变成这样子的数列(left[1,2,3,etc... ight]) ,那么我们构造(left[n,1,n-2,3,n-4 ight])就好了。
考虑构造第二问,(left[a_1,a_2,a_3,a_4,ect... ight])的前缀积相同,我们知道乘法逆元$a^{-1} imes a equiv 1 mod n (,那么我们只要把每个数都乘上前那个数的乘法逆元,这样每个位置的前缀积都等于本身)a_i mod n$了。
#include<bits/stdc++.h>
#define RP(t,a,b) for(register ll (t)=(a),edd_=(b);t<=edd_;++t)
#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)
#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)
#define Max(a,b) ((a)<(b)?(b):(a))
#define Min(a,b) ((a)<(b)?(a):(b))
#define pushup(x) seg[(x)]=seg[(x)<<1]+seg[(x)<<1|1]
#define midd register int mid=(l+r)>>1
#define chek if(R<l||r<L)return
#define TMP template<class ccf>
#define rgt L,R,mid,r,pos<<1|1
#define lef L,R,l,mid,pos<<1
#define all 1,n,1
using namespace std;typedef long long ll;
TMP inline ccf qr(ccf k){
char c=getchar();
ccf x=0;
int q=1;
while(c<48||c>57)q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
return q==-1?-x:x;
}
int X,T;ll yyb;
inline bool isp(int YYB){
for(int psj=2;psj*psj<=YYB;psj++)
if(!(YYB%psj))
return 0;
return 1;
}
const int maxn=1e5+15;
ll data[maxn];
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
X=qr(1);
T=qr(1);
if(X==1){
while(T--){
yyb=qr(1);
int psj=2;
if(yyb%psj&&yyb!=1){
puts("0 ");
continue;
}else cout<<2<<' ';
cout<<yyb<<' ';
RP(t,1,yyb-1)
cout<<((t&1)?yyb-t:t)<<' ';
puts("");
}
}
else{
while(T--){
yyb=qr(1);
if(yyb!=1&&yyb!=4&&!isp(yyb)){
puts("0 ");
continue;
}
else
cout<<2<<' ';
if(yyb==1){
puts("1 ");
continue;
}
if(yyb==4){
puts("1 3 2 4 ");
continue;
}
data[1]=1;
ll p=yyb;
RP(t,2,yyb)
(data[t]=(ll)(p-p/t)*data[p%t]%p);
cout<<1<<' ';
RP(t,2,yyb-1)
cout<<t*data[t-1]%yyb<<' ';
cout<<yyb<<' ';
puts("");
memset(data,0,sizeof data);
}
}
return 0;
}