P1853 - [NewOJ Week 13] 错排旋转

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：5 通过：1

错位排列：一个1-n的排列p，同时满足p[i]≠i。
序列a[1],a[2],...,a[n]的关于偏移量等于k旋转表示：将序列变成a[k],a[k+1],...,a[n],a[1],a[2],...,a[k-1]。
长度为n的序列存在n个不同的旋转。
给定一个错位排列D，f(D)表示存在多少个不同的旋转，使得旋转后的结果也是错位排列。
例如f([2,1])=1，[2,1]只存在1种旋转是错位排列。
f([3,1,2])=2，[3,1,2]只存在2种旋转是错位排列，分别是[3,1,2],[2,3,1]。
现在给定n和一个素数p，计算有多少个1-n的错位排列D满足f(D)=(n-2)，由于答案过大，需要对p进行取模。

输入两个数字n和p，3≤n≤1000000,10^8≤p≤10^9+7。
n表示排列长度，p为素数。

输出一个数字表示答案。

样例1：
3 1000000007

样例2：
6 999999937

样例1：
0

样例2：
20

进阶题数论

1853: [NewOJ Week 13] 错排旋转

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签