UOJ 74 题解

首先，我们需要理解题目中定义的函数f(t)。这个函数的作用是将字符串t映射成一个整数值。具体地，对于一个长度为n的字符串t，我们将其每个字符转换成对应的数字（a=0, b=1, ..., z=25），然后根据26的幂次方加权求和，并取模p。

我们知道时光机会对输入的密码旋转0到n-1次，得到n个字符串。对于每个字符串，我们可以通过f函数计算出一个对应的整数值。

题目给出了n个值h0, h1, ..., hn-1，表示时光机存储的n个值。我们需要找到一个密码s，使得对于任意0≤k<n，f(ak) = hk。

算法的关键在于求解密码s。我们可以通过反向推导，根据已知的h0, h1, ..., hn-1，以及MOD的值，来求解密码s。

在代码中，我们先通过快速幂算法计算出inv，然后根据inv的值分情况讨论：

如果inv不为0，我们可以根据公式1ll * (26ll * h[i] % MOD + MOD - h[i + 1]) % MOD * inv % MOD + 97来求解密码s。

如果inv为0，我们需要将h0, h1, ..., hn-1转换成对应的字母，然后输出即可。

 C++ 20
#import "bits/stdc++.h"
#define endl '\n'
#define ll long long

using namespace std;

const int MAX = 100100; 
int n, MOD, h[MAX], a[MAX];

int fpow(int a, int b)
{
    int s = 1;
    while(b) {
        if(b & 1)
        { s = 1ll * s * a % MOD; }
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return s;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> MOD;
    int inv = fpow(fpow(26, n) - 1, MOD - 2);
    for(int i = 0; i < n; ++i) { cin >> h[i]; }
    h[n] = h[0];
    if(inv) {
        for(int i = 0; i < n; ++i) 
        { cout << char(1ll * (26ll * h[i] % MOD + MOD - h[i + 1]) % MOD * inv % MOD + 97); }
    }
    else {
        for(int i = n - 1; ~i; --i) { a[i] = h[0] % 26, h[0] /= 26; }
        for(int i = 0; i < n; ++i) { cout << char(a[i] + 97); }
    }
    cout << endl;
    return 0;
}

chcrt0x的博客

博客

评论

发表评论