详情访问博客

题目分析

这道题目描述了一个古文明中的祭司系统，其中祭司每年会根据房间中转盘上的数字决定下一年所在的房间。题目要求我们找出第一个所有祭司都回到与自己编号相同房间的年份（即庆典年份）。

解题思路

1. 问题建模：

   • 将每个房间的转盘视为一个状态转移函数，祭司的移动路径由转盘数字决定。
   • 每年祭司移动后，转盘会逆时针旋转一格，因此每年的转移规则会动态变化。

2. 周期性分析：

   • 转盘的周期为 p 年（p 是转盘的格子数），因为每 p 年转盘会回到初始状态。
   • 因此，整个系统的状态转移具有周期性，可以将问题分解为 p 个子问题，每个子问题对应转盘的一个固定状态。

3. 循环检测：

   • 对于每个转盘状态，计算祭司的移动路径，并检测是否存在循环（即祭司最终会回到起点）。
   • 需要确保所有祭司的循环长度相同，否则无法满足所有祭司同时回到起点的条件。

4. 中国剩余定理：

   • 对于每个有效的转盘状态，将问题转化为求解一组同余方程，使用扩展欧几里得算法和中国剩余定理计算满足条件的最小年份。
   • 最终答案为所有可能转盘状态中的最小解。

5. 边界处理：

   • 若计算结果超过 10^9 或不存在解，输出“无人知晓”。

关键点

• 转盘周期：利用转盘的周期性减少计算量。
• 路径循环：检测祭司的移动路径是否形成循环，并计算循环长度。
• 同余方程：将问题转化为数学问题，使用数论工具求解。

算法选择

• 扩展欧几里得算法用于求解同余方程。
• 中国剩余定理用于合并多个同余方程的解。
• 循环检测确保所有祭司的路径同步。

这种方法高效地利用了问题的周期性，避免了暴力枚举，确保了算法在合理时间内完成。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
using namespace std;

#define LL long long
#define pii pair<int,int>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

const int N=210,INF=0x3f3f3f3f,MOD=10000,STA=8000010;
const LL LNF=0x3f3f3f3f3f3f3f3fLL;
const double DNF=1e13;

LL a[N],m[N];
int num[N][N],A[N][N],D[N][N],vis[N],vis2[N];
int n,p;

void exgcd(LL a,LL b,LL& d,LL& x,LL& y)
{
    if(!b){d=a;x=1;y=0;}
    else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}

LL Modline(int n)
{
    LL d,x,y,A,M,Mod;
    A=a[n-1],M=m[n-1];
    n--;
    // m1*x-m2*y=a2-a1
    while(n--){
        exgcd(M,m[n],d,x,y);
        if((A-a[n])%d!=0){
            return -1;
        }
        Mod=m[n]/d;
        x=(x*((a[n]-A)/d)%Mod+Mod)%Mod;
        A+=M*x;
        M=M/d*m[n];
    }
    return A;
}

int find(int T[],int C[])
{
    int i,j,u,cnt=0,d,l,t,ok;
    mem(vis,0);
    for(i=0;i<n;i++){
        if(!vis[i]){
            l=-1,d=0;u=i;
            while(!vis[u]){
                vis[u]=1;
                mem(vis2,0);
                for(t=ok=0,j=u;!vis2[j];t++,j=T[j]){
                    vis2[j]=1;
                    if(j==C[u]){ok=1;break;}
                }
                if(l==-1)l=t;
                if(!ok || l!=t)return 0;
                u=C[u];
                d++;
            }
            a[cnt]=l,m[cnt++]=d;
        }
    }
    return cnt;
}

int main()
{
    // freopen("in.txt","r",stdin);
    int i,j;
    LL ans,x;
    int t;
    while(~scanf("%d%d",&n,&p))
    {
        for(i=0;i<n;i++){
            for(j=0;j<p;j++){
                scanf("%d",&num[j][i]);
                num[j][i]--;
            }
        }
        for(i=0;i<n;i++)A[0][i]=num[0][i];
        for(i=1;i<p;i++){
            for(j=0;j<n;j++){
                A[i][j]=num[i][A[i-1][j]];
            }
        }
        for(i=0;i<p;i++){
            for(j=0;j<n;j++){
                D[i][A[i][j]]=j;
            }
        }
        
        ans=LNF;
        for(i=0;i<p;i++){
            if((t=find(A[p-1],D[i]))){
                if((x=Modline(t))!=-1){
                    ans=Min(ans,x*p+i+1);
                    if(ans>=1e9){ans=LNF;break;}
                }
            }
        }
        
        if(ans!=LNF)printf("%lld\n",ans);
        else printf("No one knows.\n");
    }
    return 0;
}