比赛链接

2020 CCPC Wannafly Winter Camp Day6 Div.1＆2

J-K重排列

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

对于一个排列 \({p[1...n]}\)，我们设 \(p^{k}[i]=p[p^{k-1}[i]]\)p
k
[i]=p[p
k−1
[i]]，且 p^{1}[i]=p[i]p
1
[i]=p[i]。
如果存在一个 {K}K，使得对于所有的 {i}i 都有 p^{K}[i]=ip
K
[i]=i，那么 {K}K 就是 {p}p 的一个周期。
给定 {n,K}n,K，你需要计算有几个 {1...n}1...n 的排列，满足 {K}K 是它的一个周期
由于答案可能很大，你只需要输出答案对 {998244353}998244353 取模后的值即可
输入描述:
第一行一个整数 {T}T 表示数据组数
对于每组数据，第一行两个正整数 {n,K}n,K
1\leq T\leq 1001≤T≤100，1\leq n\leq 501≤n≤50，1\leq K\leq 10^{18}1≤K≤10
18

输出描述:
对于每组数据，输出答案对 {998244353}998244353 取模后的值
示例1
输入
复制
5
3 10
5 100
5 120
50 1000
1 1
输出
复制
4
80
120
784037391
1

K-最大权值排列

题目描述

对于一个长度为 \({n}\) 的数列 \({A}\)，定义它的权值 \({f(A)}\)为每一个区间平均数的和，即
\(\displaystyle f(A) = \sum_{i=1}^n \sum_{j=i}^n \frac{\sum_{k=i}^j A_k}{j-i+1}\)
现在给出了整数 \({n}\)，你需要给出一个 \({1...n}\) 的排列 \({P}\) 使得 \({f(P)}\) 尽可能大。如果有多个不同的排列权值相同，则给出字典序最小的那个。
一个排列 \({a[1...n]}\) 的字典序比 \({b[1...n]}\) 的字典序小，当且仅当存在某个 \({j}\) 满足 \({a[1...j-1]=b[1...j-1]}\) 且 \({a[j]<b[j]}\)

输入描述:

一行一个正整数 \(n~(1\le n \le 10^5)\).

输出描述:

一行 \({n}\) 个数，表示答案的排列，行末需要由空格

输入

5

输出

1 3 5 4 2

解题思路

贪心

可以发现：中间出现的数的概率是最大的，所以，将大数放中间即可，由于要求字典序最小，所以，每次我们下标从 \(1\) 开始~

• 时间复杂度：\(O(n)\)

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    if(n&1)
    {
        for(int i=1;i<=n/2+1;i++)printf("%d ",2*i-1);
        for(int i=1;i<=n/2;i++)printf("%d ",n-1+(i-1)*(-2));
    }
    else
    {
        for(int i=1;i<=n/2;i++)printf("%d ",2*i-1);
        for(int i=1;i<=n/2;i++)printf("%d ",n+(i-1)*(-2));
    }
    return 0;
}