2976: [Poi2002]出圈游戏

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 132  Solved: 38
[Submit][Status][Discuss]

Description

有编号从1nn个小朋友在玩一种出圈的游戏,编号为i+1的小朋友站在编号为i小朋友左边。编号为1的小朋友站在编号为n的小朋友左边。首先编号为1的小朋友开始报数,接着站在左边的小朋友顺序报数,直到数到某个数字K时就出圈。直到所有的小朋友都出圈,则游戏完毕。游戏过程如下图所示。

Input

第一行有一个正整数n, 2 <= n <= 20,第二行有n 个整数其中第i个整数表示编号为i 的小朋友第i个出圈。

Output

求最小的K,如果不存在,则输出一个单词“NIE”

Sample Input

4
1 4 2 3

Sample Output

5

HINT

Source

[题解]ex中国剩余定理,用于模数不互质的时候.

/********************************************

	Title		BZOJ2976.cpp
	Author 		TomatoLoveCoconut
	Time		2018-4-03
	History		Created 2018-4-03
	
	Version		1.0.0
	
	Tags:		ExCRT
			Exgcd


	while(true) RP++;
	
		 QAQ

*********************************************/


#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define base 311
#define mod 19270817
#define maxlongint 2147483647
#define maxint 32767
#define pi (double)acos(-1.0)
#define eps 1e-9
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
//SGT
#define MID ((l+r)>>1)
#define lson (o<<1)
#define rson (o<<1|1)
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a));
#define clc(a) memset(a,-1,sizeof(a));



using namespace std;


//complex
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
};
inline Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
inline Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
inline Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x);}
//BIT
inline int lowbit(int x){return x&(-x);}




//var
int n;
int num[25];
int M[25],R[25];
int vis[25];
inline int exgcd(int a,int b,int &x,int &y)
{
	if (!b)
	{
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return d;
}
inline int excrt()
{
	int m=M[1],r=R[1];
	int x,y,d;
	for (int i=2;i<n;i++)
	{
		d=exgcd(m,M[i],x,y);
		if ((R[i]-r)%d) return -1;
		r=(R[i]-r)/d*x%(M[i]/d)*m+r;
		m=m*(M[i]/d);
		r=r%m;
	}
	r=(r+m)%m;
	if (r==0) r=m;
	return r;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	int x;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		num[x]=i;
	}
	int pos=1;
	for (int i=1;i<n;i++)
	{
		M[i]=n-i+1;
		int cnt=0;
		for (int j=pos;j;j++)
		{
			if (j>n) j=1;
			if (!vis[j]) cnt++;
			if (j==num[i])
			  break;
		}
		vis[num[i]]=1;
		R[i]=cnt;
		pos=num[i]+1;
	}
	int ans=excrt();
	if (ans==-1)
		puts("NIE");
	else printf("%d\n",ans);
	return 0;
}













/****************************************************
		Any Questions Please Contact Me
		Tencent QQ:	898021802
		Website:	primopan.org
		Email:		primojpan@gmail.com
****************************************************/

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注