#P5263. 咏叹

    ID: 4301 传统题 2000ms 233MiB 尝试: 6 已通过: 4 难度: 4 上传者: 标签>CF1600普及+/提高-冒泡排序势能分析直接模拟ByC_SUNSHINE

咏叹

题目描述

给定一个由 1,…,n1,\ldots,n 组成的排列 AA。若它尚未升序排列,就从左到右扫描 i=1,…,n−1i=1,\ldots,n-1,遇到 Ai>Ai+1A_i>A_{i+1} 就交换这两个元素。一次完整扫描记为一轮。求使排列升序所需的轮数。初始已升序时,轮数为 00。

输入格式

一行五个整数 n,S,B,C,Dn,S,B,C,D。用下列过程生成初始排列,下标从 11 开始。

for i = 1 .. n:
    A[i] = i
    S = (S * B + C) mod D
    swap(A[i], A[(S mod i) + 1])

输出格式

输出一个整数,表示所需的轮数。

样例

4 5 7 9 13
2

数据范围

  • 30%30\% 的数据满足 n≤103n\le 10^3。
  • 50%50\% 的数据满足 n≤105n\le 10^5。
  • 70%70\% 的数据满足 n≤106n\le 10^6。
  • 所有数据满足 1≤n≤3×1071\le n\le 3\times 10^7,0≤S,B,C<D≤109+70\le S,B,C<D\le 10^9+7。

原 PDF 题面第 1 页 · 原 PDF 题面第 2 页