P2391 白雪皑皑

    • 269通过
    • 832提交
  • 题目提供者 nonprocess
  • 评测方式 云端评测
  • 标签 并查集 模拟 福建省历届夏令营 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    “柴门闻犬吠,风雪夜归人”,冬天,不期而至。千里冰封,万里雪飘。空中刮起了鸭毛大雪。雪花纷纷,降落人间。 美能量星球(pty 在 spore 上的一个殖民地)上的人们被这美景所震撼。但是 pty 却不高兴,他不喜欢白色的世界,他觉得这样太单调了。所以他想对雪花进行染色,让世界变得多彩些。

    题目描述

    现在有 N 片雪花排成一列。 Pty 要对雪花进行 M 次染色操作,第 i次染色操作中,把第(i*p+q)%N+1 片雪花和第(i*q+p)%N+1 片雪花之间的雪花(包括端点)染成颜色 i。其中 p,q 是给定的两个正整数。他想知道最后 N 片雪花被染成了什么颜色。

    输入输出格式

    输入格式:

    包含 4 行:

    N M p q 意义如题中所述。

    输出格式:

    包含 N 行:

    第 i 行表示第 i 片雪花被染成的颜色 c

    输入输出样例

    输入样例#1: 复制
    4
    3
    2
    4
    输出样例#1: 复制
    2
    2
    3
    0

    说明

    20%的数据满足:1<=n,m<=1000

    40%的数据满足:1<=n<=8000,1<=m<=1000000

    80%的数据满足:1<=n<=500000,1<=m<=10000000

    100%的数据满足:1<=n<=1000000,1<=m<=10000000

    保证 1<=M*p+q,M*q+p<=2*10^9

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。