2020牛客暑期多校训练营（第六场）E

题目描述

Roundgod is given n, k, construct a permutation $P$ of $1\sim n$ satisfying that for all integers $i$ in $[1, n]$ , there exists a contiguous subarray in $P$ of length $i$ whose sum is kk modulo nn. If there are multiple solutions, print any of them. If there is no solution, print "-1" in one line.

输入描述

The first line contains two integers $n$ , $k$ $(1\leqslant n \leqslant 5000, 0\leqslant k < n)$ .

输出描述

Print $n$ integers, the answer permutation in one line if such permutation exists, or print "-1" in one line if no solution exists.

示例1

输入

2 1

输出

1 2

说明

The sum of subintervals $[1],[1,2]$ both satisfy $\equiv 1 \pmod{2}$ , and their lengths are $1,2$ respectively.

示例2

输入

3 1

输出

-1

分析

$\forall\ i\in[1,n]$ ， $P$ 存在子列满足，子列各个元素的和与 $k$ 模 $n$ 同余；当 $i=n$ 时，子列的和为 $\sum\limits_{i=1}^n P_i=\sum\limits_{i=1}^n i=\frac{n(n+1)}{2}$ ，故 $\frac{n(n+1)}{2}\equiv k\pmod n$ 。
当 $n$ 为奇数，若 $k=0$ ，则有解；令 $P=[n,1,n-1,2,n-2,\cdots]$ 即可。
当 $n$ 为偶数，若 $k=\frac{n}{2}$ ，则有解；令 $P=\left[n,\frac{n}{2},1,n-1,2,n-2,\cdots\right]$ 即可。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem E
Date: 8/24/2020
Description: Construction
*******************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    if(n&1){
        if(!k){
            cout<<n;
            for(register int i=1;i<=n/2;i++){
                printf(" %d %d",i,n-i);
            }
            putchar('\n');
        }else{
            puts("-1");
        }
    }else{
        if(k==n/2){
            cout<<n<<' '<<n/2;
            for(register int i=1;i<n/2;i++){
                printf(" %d %d",i,n-i);
            }
            putchar('\n');
        }else{
            puts("-1");
        }
    }
    return 0;
}