poj 1282 庆典的日期置换群

　　根据题意，N个编号祭祀，N个房间，每个转盘上有P个数字，且每年保证每个房间有且仅有一个祭祀。

　　可以转换成 P 个不同的 N元组置换。

　　其中 $T_{i}$ 为第i天祭祀位置， $D_{i}$ 为第 i 天转盘置换

　　则第i天祭祀所在的房间为 $T_{i} = D_{i}\cdot T_{i-1}$ （为什么是先D后T，因为置换的乘法是连接，先 $T_{i}$ 后 $D_{i}$ ）

　　题目要求经过 Y天，得到单位置换，且总共P个不同的置换所以我们可以得到如下形式：

　　 $T_{k-1}\cdot...\cdot T_{0} \cdot T_{p-1} \cdot \cdot \cdot T_{1} \cdot T_{0} \cdot \cdot \cdot T_{p-1} \cdot \cdot \cdot T_{1} \cdot T_{0} = e$ （其中 e 为单位置换）

　　假设 Y mod p = k , 则可表示成如下形式：

　　 $( T_{k-1}\cdot...\cdot T_{0} ) \cdot ( T_{p-1} \cdot \cdot \cdot T_{1} \cdot T_{0} )^{ (y-k)/p }= e$

　　再转换一下：

　　 $( T_{k-1}\cdot...\cdot T_{0} )^{-1} = ( T_{p-1} \cdot \cdot \cdot T_{1} \cdot T_{0} )^{ (y-k)/p }$ 　

　　令 x = （y - k ）/ p ， $T_{step}= ( T_{p-1} \cdot \cdot \cdot T_{1} \cdot T_{0} )^{ (y-k)/p }$ ， $T_{head} = ( T_{k-1}\cdot...\cdot T_{0} )$ 得到

　　上式转换成：

　　　 $T_{step}^{X} = T_{head}^{-1}$ 　

　　　对于 $T_{step}$ 　， $T_{head}^{-1}$ 我们通过预处理得出，然后枚举 K

　　 $T_{step}$ 的 X 次幂，转换成 $T_{head}^{-1}$ ， N个元组相对应，我们可用通过置换模拟，求出每一个元组的 ( Ri, Ai ) 从而得到一个模同余方程组。

　　求解方程组，得到X，然后得出Y。

解题代码：

View Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;

typedef long long LL;
const int N = 210;
const LL inf = 1e9;
int A[N][N], T[N][N], D[N][N], p, n;
int r[N], a[N];// X = r[i] ( mod a[i] )

bool find( int Q[], int key, int k, int &rr, int &aa )
{
    int s = Q[k]; 
    rr = -1; aa = 1;
    if( k == key ) rr = 0;
    while( s != k )
    {    
        if( s == key ) rr = aa;
        aa++;
        s = Q[s];
    }
    return (rr == -1) ? false : true;
}
LL ExGcd( LL a, LL b, LL &x, LL &y )
{
    if( b == 0 ) { x=1;y=0; return a;}
    LL r = ExGcd( b, a%b, x, y );
    LL t = x; x = y; y = t-a/b*y;
    return r;
}
LL ModLine( )
{
    LL rr = r[0], aa = a[0];
    for(int i = 1; i < n; i++)
    {
        // r[i] - rr = aa*x + a[i]*y    
        LL x, y, C = r[i]-rr;
        LL d = ExGcd( aa, a[i], x, y );
        if( C%d != 0 ) return -1;
        LL Mod = a[i]/d;
        x = ((x*(C/d)%Mod)+Mod)%Mod;
        rr = rr + aa*x;
        aa = aa*(a[i]/d);
    }
    return rr;
}
int main()
{
    while( scanf("%d%d", &n, &p) != EOF)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < p; j++)
            {
                scanf("%d", &A[j][i] );
                A[j][i]--; // (0,1,2,...,n-1)
            }
        }
        for(int i = 0; i < n; i++)
            T[0][i] = A[0][i];
        for(int i = 1; i < p; i++)
        { // T[p-1]*T[p-2]*...*T[0]  置换乘法为连接，且左后右先
            for(int j = 0; j < n; j++)
                T[i][j] = A[i][ T[i-1][j] ];
        }
        for(int i = 0; i < p; i++ )
        { // 求逆
            for(int j = 0; j < n; j++)
                D[i][ T[i][j] ] = j;
        }
        LL res = inf;    
        // 枚举 Y % p = k, x = (Y-k)/p 
        for(int k = 0; k < p; k++)
        {// T[p-1]^x = D[k]
            bool flag = true;
            for(int i = 0; (i < n) && flag; i++)
                if( !find( T[p-1], D[k][i], i, r[i], a[i] ) ) flag = false;
            if( !flag ) continue;    
            LL x = ModLine();
            if( ( x != -1 ) && ( x*p+k+1 < res ) )
                res = x*p+k+1;    
        }
        if( res == inf ) puts("No one knows.");
        else    printf("%lld\n", res );
    }
    return 0;
}

poj 1282 庆典的日期 置换群

poj 1282 庆典的日期置换群