Zby2001

NC231998. Zby2001

描述

Zby2001 is a very clever boy.

One day sjie gives him a problem:

Giving Zby2001 an array P of length $n(1\le n\le 1000000)$ . For every $0\le i\lt n$ , i appears exactly once in the array P. Zby2001 can do the following operations any times:

Change $P_i \to (P_i+1) \ mod \ n$ for every $0\le i\lt n.$

Change $P \to Q$ ,such that $Q_{P_i}=i$ for every $0\le i\lt n .$

Sjie asks how many different arrays he can get. (For two arrays A and B, if there exists an integer i such that $A_i \ne B_i$ , they are different.)

Zby2001 doesn't think the problem is worth doing. So sjie asks you for help.

输入描述

The first line contains a single integer 
The second line contains n integers , represents the array P. It is guaranteed that P is a permutation from 0 to n-1.

输出描述

Print a single integer, represents how many different arrays you can get.

示例1

输入:

4
0 1 2 3

输出:

说明:

Insample1, 4 arrays you can get are:

P1= [0,1,2,3]

P2= [1,2,3,0]

P3= [2,3,0,1]

P4= [3,0,1,2]

示例2

输入:

4
0 2 1 3

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 113ms, 内存消耗: 32632K, 提交时间: 2022-01-27 22:49:53

#include<bits/stdc++.h>
using namespace std;
const int M=2e6+9;
int n,x,y;
int a[M],b[M],f[M],s1[M],s2[M];
bool vis[M];
int main() {
	scanf("%d",&n);
	for(int i=0; i<n; ++i)scanf("%d",&a[i]),b[a[i]]=i,vis[i]=0;
	for(int i=0; i<n; ++i) {
		vis[a[i]]=1;
		s1[i+1]=(a[i]+n-a[i?i-1:n-1])%n;
		s2[i+1]=(b[i]+n-b[i?i-1:n-1])%n;
		s1[n+i+1]=s1[i+1];
		s2[n+i+1]=s2[i+1];
	}
	for(int i=0; i<n; ++i)assert(vis[i]==1);
	for(int i=1,j=0; i<=n*2; f[++i]=++j)while(j&&s1[i]!=s1[j])j=f[j];
	x=n*2+1-f[n*2+1];
	for(int i=1,j=0; i<=n*2; f[++i]=++j)while(j&&s2[i]!=s2[j])j=f[j];
	y=n*2+1-f[n*2+1];
	bool bol=0;
	if(x==y) {
		for(int i=1,j=1; i<=n*2; ++i,++j) {
			while(j&&s1[i]!=s2[j])j=f[j];
			if(j==x) {
				bol=1;
				break;
			}
		}
	}
	printf("%lld\n",1ll*(x+(bol?0:y))*n);
	return 0;
}