構造+數論+打表——Koishi Loves Construction

題解：

首先對于X=1和X=2都dfs一下打表找規律，X=1的時候規律很好找隻是需要注意一下，n不能為奇數，否則前n-1項和一定是n的倍數那麼模n的意義下一定會出現至少兩個相同的數。然後1的時候是可以的。

X=2的時候也是打表可以發現， s u m i ≡ i ( m o d n ) sum_i ≡i(mod n) sumi​≡i(modn)。是以知道要處理字首積的逆元。然後n必須為質數否則 n ∣ ( n − 1 ) ! n|(n-1)! n∣(n−1)!，特判一下1和4。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int prime[N],vis[N],cnt,n;
void init()
{
    vis[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<N;j++){
            vis[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}
void solve1()
{
    scanf("%lld",&n);
    if((n&1)&&(n^1)) printf("0\n");
    else{
        printf("2 ");
        for(int i=1;i<=n;i++){
            if(i&1) printf("%lld%c",n-i+1,i==n?'\n':' ');
            else printf("%lld%c",i-1,i==n?'\n':' ');
        }
    }
}
int q_pow(int a,int b)
{
    int res=1;
    while(b){
        if(b&1) res=res*a%n;
        a=a*a%n;
        b>>=1;
    }
    return res%n;
}
void solve2()
{
    scanf("%lld",&n);
    if(vis[n]&&(n^1)&&(n^4)) puts("0");
    else{
        if(n==1) printf("2 1\n");
        if(n==4) printf("2 1 3 2 4\n");
        else{
            int tmp=1,sum=1;
            printf("2");
            for(int i=1;i<=n-1;i++){
                printf(" %lld",tmp);
                tmp=q_pow(sum,n-2)%n*(i+1)%n;
                sum=sum*tmp%n;
            }
            printf(" %lld\n",n);
        }
    }
}
signed main()
{
    init();
    int x,t; scanf("%lld%lld",&x,&t);
    for(int i=1;i<=t;i++){
        if(x==1) solve1();
        else solve2();
    }
}