题解归档 - cf932C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf932C
• 本地来源：problems/cf932C/idea.md
• 题目链接：https://codeforces.com/contest/932/problem/C
• 原始标题：932C Permutation Cycle

思路

932C Permutation Cycle

题意

给定 (N,A,B)，构造 (1\ldots N) 的排列 (P)。定义 (f(i,j)) 为从 (i) 出发沿 (P) 走 (j) 步到达的位置，(g(i)) 为最小正整数 (j) 使 (f(i,j)=i)（即 (i) 所在置换环的长度）。

要求对每个 (i)，(g(i)\in{A,B})；无解输出 -1。

关键观察

(g(i)) 等于 (i) 在置换分解中所在环的长度。因此问题等价于：能否把 ({1,\ldots,N}) 划分成若干个不相交环，且每个环长只能是 (A) 或 (B)。

充要条件：存在非负整数 (x,y) 使 (xA+yB=N)。

• (A=B) 时即 (N) 能被 (A) 整除。
• 一般情况枚举 (x\in[0,\lfloor N/A\rfloor])，检查 (N-xA) 是否被 (B) 整除。

构造

找到一组 ((x,y)) 后，从 cur=1 依次放置：

• (x) 个长为 (A) 的环：p[cur..cur+A-2]=cur+1..cur+A-1，p[cur+A-1]=cur；
• (y) 个长为 (B) 的环，同理。

复杂度

时间 (O(N))，空间 (O(N))。

验证

样例 9 2 5 → 2 1 4 3 6 7 8 9 5；3 2 1 可取全不动点 1 2 3。

代码

来源：problems/cf932C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:24:06
**/
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
using namespace std;
ll p[maxn];
int main(){
    ll n,a,b,i,j,k,cur,x,y,zc;
    cin>>n>>a>>b;
    if(a==b){
        if(n%a){
            cout<<-1<<"\n";
            return 0;
        }
        x=n/a;
        y=0;
    }else{
        zc=0;
        for(i=0;i*a<=n;i++){
            if((n-i*a)%b==0){
                x=i;
                y=(n-i*a)/b;
                zc=1;
                break;
            }
        }
        if(!zc){
            cout<<-1<<"\n";
            return 0;
        }
    }
    cur=1;
    for(i=0;i<x;i++){
        for(j=0;j<a-1;j++) p[cur+j]=cur+j+1;
        p[cur+a-1]=cur;
        cur+=a;
    }
    for(i=0;i<y;i++){
        for(j=0;j<b-1;j++) p[cur+j]=cur+j+1;
        p[cur+b-1]=cur;
        cur+=b;
    }
    for(i=1;i<=n;i++){
        cout<<p[i];
        if(i<n) cout<<" ";
    }
    cout<<"\n";
    return 0;
}