P3599 Koishi Loves Construction

ooliver的头像 发布于 2026-02-11 79 次阅读 OI

P3599 Koishi Loves Construction

对于 Task 1，首先 nn 肯定要放在第一个，否则会出现两个前缀和模 nn 相等。

其次考虑 nn 为奇数的情况显然是不成立的，因为总和为 n(n+1)2\frac{n(n+1)}{2}，显然模 nn 为 0，同样会出现两个前缀和模 nn 相等。

考虑打表，发现一种构造形式，正确性读者自证不难，两两结合着看即可：

n, n−1, 2, n−3, 4, ..., 1n,\ n-1,\ 2,\ n-3,\ 4,\ ...,\ 1

对于 Task 2，考虑 1 要放在第一个，nn 要放在最后一个，可以构造一个分数序列：

1,21,32,...,n1,\frac{2}{1},\frac{3}{2},...,n

不难证明求逆元后的余数与 [0,n)[0,n) 中的数一一对应，所以就做完了。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int x,T;
int n,idx;
int vis[N],prm[N],isprm[N];

void prime(){
	for(int i=2;i<N;i++){
		if(!vis[i]) prm[++idx]=i,isprm[i]=1;
		for(int j=1;1ll*i*prm[j]<N;j++){
			vis[i*prm[j]]=1;
			if(i%prm[j]==0) break;
		}
	}
}

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=n;
        (x*=x)%=n,y>>=1;
    }
    return res;
}

signed main(){
    prime();
    cin>>x>>T;
    while(T--){
        cin>>n;
        if(x==1){
            if(n==1){
                cout<<"2 1\n";
                continue;
            }
            else if(n&1){
                cout<<"0\n";
                continue;
            }
            cout<<"2 "<<n<<" ";
            int cnt1=n-1,cnt2=2;
            for(int i=2;i<n;i+=2){
                cout<<cnt1<<" "<<cnt2<<" ";
                cnt1-=2,cnt2+=2;
            }
            cout<<"1\n";
        }
        if(x==2){
            if(n==1){
                cout<<"2 1\n";
                continue;
            }
            if(n==4){
                cout<<"2 1 3 2 4\n";
                continue;
            }
            if(!isprm[n]){
                cout<<"0\n";
                continue;
            }
            cout<<"2 1 ";
            for(int i=1;i<=n-2;i++) cout<<(1+qpow(i,n-2))%n<<" ";
            cout<<n<<"\n";
        }
    }
	return 0;
}