题解：P12952 [GCJ Farewell Round #2] Intruder Outsmarting

jsisonx · 2025-07-03 11:33:16 · 题解

题目传送门

题目分析

注意到，首先，转动转轮的过程实际上就是加 D 再模 N 的过程。第二，回文串的性质是 X_i=X_{w-i+1}。根据以上两点，该题可解。

由上面两点不难看出，题目实际上是要求下面同余方程的解：

其中 i 取遍 1 到 \lfloor \frac{N}{2} \rfloor。

上面的同余方程变形得

这是一个二元一次不定方程。根据裴蜀定理，有解的充分必要条件是 X_{w+i-1}-X_i 是 (D,N) 的倍数。因此，若存在 i 使得 X_{w+i-1}-X_i 不是 (D,N) 的倍数，则无解。

若有解，则使用扩展欧几里得算法求出方程的一组解。设 x-y=p。

由于转动第 i 个和第 w-i+1 个转轮不会影响其他转轮，因此只需求出 x+y 的最小值。

由于扩展欧几里得算法求出的解有正有负，因此需要分类讨论。

若 p \ge 0，则 x=y+p，此时 x+y=2y+p。显然最小值在 y=0 且 p 为不定方程最小非负整数解时取到，为 p。

若 p<0，则设 p_0=-p，有 y-x=p_0，即 x+y=2x+p_0，显然最小值在 x=0 且 p_0 为最大负整数解的相反数，即 p 取到最大负整数解时取到，为 p_0。

因此，只需取最小非负整数解和最大负整数解的相反数中较小值即可。

对于不定方程 Dx+Ny=C，我们有 x=x_0-\frac{N}{(D,N)}t，其中 x_0 为一个特解，t 为任意整数。因此，若求最小非负整数解，只需找到最大的 t 使得 x 为正整数。易证此时 x=x_0 \bmod n_0，其中 n_0=\frac{N}{(D,N)}，所以最小非负整数解为 x=x_0 \bmod n_0。显然，最大负整数解为 (x_0 \bmod n_0)-n_0，所以最大负整数解的相反数为 n_0-(x_0 \bmod n_0)。

综上，对于第 i 个转轮和第 w-i+1 个转轮，最少需要转 \min(x_0 \bmod n_0,n_0-(x_0 \bmod n_0)) 次。

代码

#include<bits/stdc++.h>
#define N 2001
using namespace std;
long long x,y;
long long gcd(long long a,long long b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
void exgcd(long long a,long long b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    long long t=x;
    x=y;
    y=t-a/b*y;
}
long long ans=0;
long long a[N];
int main(){
    int t;
    cin>>t;
    for(int o=1;o<=t;o++){
        ans=0;
        cout<<"Case #"<<o<<": ";
        int w,yes=1;
        long long n,d;
        cin>>w>>n>>d;
        for(int i=1;i<=w;i++){
            cin>>a[i];
        }
        long long g0=gcd(n,d);
        for(int i=1;i<=w/2;i++){
            if((a[i]-a[w-i+1])%g0!=0){
                yes=0;
                cout<<"IMPOSSIBLE"<<endl;
                break;
            }
            exgcd(d,n);
            long long n0=n/g0;
            x=x*(((a[w-i+1]-a[i])/g0)%n0)%n0;
            //cout<<x<<" "<<y<<endl;
            //int nas0=ans;
            if(x>=0){
                x%=n0;
                ans+=min(x,n0-x);
            }
            else{
                long long x0=x+n0*(ceil((double)(-x)/(double)n0));
                //cout<<x0<<endl;
                ans+=min(x0,n0-x0);
            }
            //cout<<ans-nas0<<endl;
        }
        if(yes){
            cout<<ans<<endl;
        }
    }
    return 0;
}