rt,第一个点一直 WA,别的点都能过。有做过这道题的大佬说一下本题坑点也行…
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,f=1;
char c=getchar();
while(c<'0'||'9'<c){
if(c=='-') f=-1;
c=getchar();
}
while('0'<=c&&c<='9'){
ret=(ret<<1)+(ret<<3)+(int)(c-'0');
c=getchar();
}
return ret*f;
}
inline long long readll(){
long long ret=0ll,f=1ll;
char c=getchar();
while(c<'0'||'9'<c){
if(c=='-') f=-1ll;
c=getchar();
}
while('0'<=c&&c<='9'){
ret=(ret<<1ll)+(ret<<3ll)+(long long)(c-'0');
c=getchar();
}
return ret*f;
}
inline void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10) write(x/10);
putchar('0'+x%10);
}
inline void writell(long long x){
if(x<0ll){
putchar('-');
x=-x;
}
if(x>=10ll) writell(x/10ll);
putchar('0'+x%10ll);
}
typedef long long LL;
#define int long long
const int NR=25;
int a[NR],n[NR];
int d,x,y;
inline void exgcd(int a,int b){
if(b==0){
d=a;
x=1;
y=0;
return;
}
exgcd(b,a%b);
int t=x;
x=y;
y=t-(a/b)*y;
}
inline int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
inline int lcm(int a,int b){
return a/gcd(a,b)*b;
}
inline int qmul(int x,int k,int MOD){
if(k==0) return 0;
int tmp=qmul(x,k>>1ll,MOD);
tmp=(tmp+tmp)%MOD;
if(k&1ll) tmp=(tmp+x)%MOD;
return tmp;
}
inline void excrt(int N){
int _lcm;
for(int i=2;i<=N;i++){
if(a[i]<a[i-1]){
swap(a[i],a[i-1]);
swap(n[i],n[i-1]);
}
exgcd(n[i-1],n[i]);
if((a[i]-a[i-1])%d!=0){
puts("NIE");
return;
}
x=qmul(x,(a[i]-a[i-1])/d,(n[i]/d));
x=(x%(n[i]/d)+(n[i]/d))%(n[i]/d);
// if(x==0) x=(n[i]/d);
_lcm=lcm(n[i-1],n[i]);
a[i]=(a[i-1]+qmul(x,n[i-1],_lcm))%_lcm;
n[i]=_lcm;
}
cout<<(a[N]==0?n[N]:a[N])<<'\n';
}
bool vis[NR];
signed main(){
// ios::sync_with_stdio(false);
int N=read();
for(int i=1,now=1,ix,cnt=0;i<=N;i++){
ix=read();
if(vis[ix]==true){
puts("NIE");
return 0;
}
vis[ix]=true;
cnt=0;
while(now!=ix){
if(vis[now]==false) cnt++;
now=(now%N)+1;
}
now=(ix%N)+1;
a[i]=(cnt+1)%(N-i+1);
n[i]=N-i+1;
}
excrt(N);
return 0;
}
/*
1 2 3 4 (1 -> %4=1)
2 3 4 (4 -> %3=0)
2 3 (3 -> %2=0)
2 (2 -> %1=0)
x=p*n[i-1]+a[i-1]=q*n[i]+a[i]
p*n[i-1]-q*n[i]=a[i]-a[i-1]
*/