#P3949. 买置换

    ID: 3155 传统题 1000ms 256MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-置换循环分解最小公倍数欧拉函数试除法分解质因数模逆元离线预收集坐标离散化FHQ Treap 分裂合并按排名分裂哈希表增量维护2014年国家集训队十五人互测

买置换

题目描述

买菜否开了一家店,号称「一切皆可买」,生意红火。

这天 crx 看到店里面有一个很长的置换 AA,它的形式非常优美。若将其表示成排列 (a1,a2,…,an)(a_1,a_2,\ldots,a_n),则对所有 1≤i≤n1\le i\le n 都有

ai=i mod n+1.a_i=i\bmod n+1.

买菜否表示,只要 crx 能求出 AA 的特征值,就让 crx 低价买下这个置换。

对任意一个置换 PP,定义它的特征值为:PP 能生成的所有不同置换的循环数之和。其中,“能生成”是指 PP 的一个或多个幂(反复与自身复合),循环数是将置换分解成互不相交的循环后,循环的个数。只需输出特征值模 109+710^9+7 的结果。

买菜否依次进行了 qq 次操作。每次给定两个不同的整数 x,yx,y,把排列中数值为 xx 和数值为 yy 的两个元素交换(不是交换下标为 x,yx,y 的两个位置)。求每次操作完成后当前置换的特征值。

输入格式

第一行两个整数 n,qn,q,表示置换长度和操作次数。

接下来 qq 行,每行两个整数 x,yx,y,表示交换当前排列中数值为 xx、yy 的两个数。

输出格式

输出 qq 行,第 ii 行一个整数,为第 ii 次操作后置换的特征值对 109+710^9+7 取模的结果。

样例输入

4 2
4 3
1 3

样例输出

8
8

样例说明

第一次交换后,置换为 (2,4,3,1)(2,4,3,1)。它产生三个不同置换,循环数依次为 2,2,42,2,4,因此答案为 88。

第二次交换后,置换为 (2,4,1,3)(2,4,1,3),是一个长度为 44 的单循环,其特征值为 88。

数据范围

  • 1≤n≤1081\le n\le10^8。
  • 1≤q≤1051\le q\le10^5。
  • 1≤x,y≤n1\le x,y\le n 且 x≠yx\ne y。

特别说明:由于 q≥1q\ge1 且 x≠yx\ne y,不存在满足所有输入限制的 n=1n=1 测试数据。正式数据均取 n≥2n\ge2。