第二届 Hello World 程序设计竞赛题解

Hello_World

A. 舍罕王的反击

题意

给定 $x$，要求构造一个等比数列，该数列首项为 $1$，公比为 $q$，前 $n$ 项和等于 $x$，输出最小的满足条件的正整数 $q$ 以及对应的 $n$。

数据范围

对于 $100\%$ 的数据，$1\leq x\leq10^9$

题解

最小的正整数为 $1$，当 $q=1$ 时可以发现，必然有满足条件的 $n=x$。

标程

#include <stdio.h>
int x;
int main() {
    scanf("%d", &x);
    printf("1 %d\n", x);
    return 0;
}

B. 小班教学

题意

$Hello~World$ 的所有会员总共想学 $n$ 种语言，有 $a_i$ 个人想学第 $i$ 种语言，要求对所有会员分班，使得满足每个班的人数相等，且每个班内学习的语言相同。

数据范围

对于 $50\%$ 的数据，$1\leq n\leq10^4,1\leq a_i\leq10^3$
对于 $70\%$ 的数据，$1\leq n\leq10^4,1\leq a_i\leq10^6$
对于 $100\%$ 的数据，$1\leq n\leq10^6,1\leq a_i\leq2^{31}-1$，答案不超过 int 能表示的范围

题解

第一种暴力解法是枚举所有可能的每个班级的人数，由班级人数计算需要分班的数量，取最小值，最开始给的数据是可以通过一些 break 优化卡过去的，后来加强了最后三组数据，让这种暴力做法只能得到 $70\%$ 的分数。
由于每个班级的人数越多，分班数量越少，而且要求满足每种语言的分班人数都相等，所以每个班的人数都要能整除每一种语言的人数，因此每个分班的最大人数就是这 $n$ 个数字的最大公约数，求最大公约数用辗转相除法，暴力枚举最大公约数的话，也是无法通过最后三组数据。
最后注意虽然答案在 int 范围内，但是 $n$ 个数字的和是在 long long 范围的，当然也可以像标程这样来控制计算过程中不爆 int。

标程

#include <stdio.h>
int n, ans, Gcd;
int num[1000000 + 100];
int gcd(int a, int b) {
    if(b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
int main() {
    ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &num[i]);
    }
    Gcd = num[0];
    for(int i = 1; i < n; ++i) {
        Gcd = gcd(Gcd, num[i]);
    }
    for(int i = 0; i < n; ++i) {
        ans += num[i] / Gcd;
    }
    printf("%d\n", ans);
    return 0;
}

C. 小 Hi 的情书

题意

原先有 $n$ 个单词，将每个单词按照下面的规则加密：

1. 对每个单词进行加密
2. 不改变单词的大小写
3. 针对每个单词，从第一个字母开始标序号，到最后一个字母，取出所有序号为奇数的字母，连起来作为加密后单词的前半部分。再倒着取出所有序号为偶数的字母，作为单词的后半部分

输入加密后的单词，输出解密后的单词。

数据范围

整篇情书的字母数量之和不大于 $5000$

题解

用两个下标在单词两端扫描，一个从左往右扫，另一个从右往左扫，来填充原单词，当处于原单词奇数位的时候，取左边的下标对应的字母，当处于原单词偶数位的时候，取右边的下标对应的字母，两个下标不断往中间靠拢，直到填满整个单词。

标程

#include <stdio.h>
#include <string.h>
int n, l, r, len;
char str[5000 + 100], ans[5000 + 100];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%s", str);
        len = strlen(str);
        l = 0;
        r = len - 1;
        for(int j = 1; j <= len; ++j) {
            if(j % 2 == 1) {
                ans[j] = str[l];
                ++l;
            } else {
                ans[j] = str[r];
                --r;
            }
        }
        ans[len + 1] = '\0';
        printf("%s ", ans + 1);
    }
    printf("\n");
    return 0;
}

D. 小 Hi 的 $RP$

题意

给出 $7$ 个 $[0,9]$ 范围内的整数，可以对这 $7$ 个整数进行任意多次的加减操作，若对某个数字进行加一操作，必须要选择另一个数字做减一操作，要求最后得到的 $7$ 个数字的乘积最大。

数据范围

对于 $50\%$ 的数据，$0\leq a_1+a_2+\cdots+a_7\leq20$
对于 $100\%$ 的数据，$1\leq T\leq100,0\leq a_i\leq9$

题解

由于对其中一个数字加一就要对另一个数字减一，因此 $7$ 个数字的总和始终不变，第一种做法是在保持总和不变的情况下暴力递归枚举每一种分配的方式，由于 $T$ 有 $100$，因此这种做法一组数据都通过不了。
考虑只有两个数字的情况，由基本不等式可以得到，要使得乘积最大必须要尽量平均分这两个数字，对其扩展证明可以得到，只要尽量平均分配这 $7$ 个数字的和，就可以得到最大的乘积。令 $sum=a_1+a2+\cdots+a_7,mod=sum\%7$，可知 $7$ 个数中有 $7-mod$ 个数字被分配为 $\lfloor\frac{sum}{7}\rfloor$，有 $mod$ 个数被分配为 $\lfloor\frac{sum}{7}\rfloor+1$，因此答案为：

$$ans=\left\lfloor\frac{sum}{7}\right\rfloor^{7-mod}\times\left(\left\lfloor\frac{sum}{7}\right\rfloor+1\right)^{mod}$$

这种做法可能是大多数人猜结论都可以猜出来的做法。
由于验题人并不会对基本不等式扩展进行严格的证明，因此用了第三种解法。定义 $dp[i][j]$ 表示前 $i$ 个数字的和为 $j$ 时能得到的最大乘积。第 $i$ 个数字可以取的合法范围为 $[0,\min(9,j)]$，枚举第 $i$ 个数字可能的取值，可以得到递推式：

$$dp[i][j]=\max(dp[i-1][j-k]\times k)\quad\quad k\in[0,\min(j,9)],j-k\leq(i-1)\times9$$

初始条件为 $dp[1][j]=j,j\in[0,9]$，最后的答案就是 $dp[7][sum]$，也就是前 $7$ 个数字的和为 $sum$ 时乘积的最大值。

标程

std1.c

#include <stdio.h>
int T, sum, x, mod;
int Pow[20][20];
int main() {
    for(int i = 1; i <= 10; ++i) {
        Pow[i][0] = 1;
        for(int j = 1; j <= 7; ++j) {
            Pow[i][j] = Pow[i][j - 1] * i;
        }
    }
    scanf("%d", &T);
    while(T--) {
        sum = 0;
        for(int i = 0; i < 7; ++i) {
            scanf("%d", &x);
            sum += x;
        }
        mod = sum % 7;
        printf("%d\n", Pow[sum / 7][7 - mod] * Pow[sum / 7 + 1][mod]);
    }
    return 0;
}

std2.c

#include <stdio.h>
int T, x, sum, up;
int dp[20][100];
int min(int a, int b) {
    if(a < b) {
        return a;
    }
    return b;
}
int max(int a, int b) {
    if(a > b) {
        return a;
    }
    return b;
}
int main() {
    for(int i = 0; i <= 9; ++i) {
        dp[1][i] = i;
    }
    for(int i = 2; i <= 7; ++i) {
        for(int j = 0; j <= i * 9; ++j) {
            dp[i][j] = 0;
            up = min(9, j);
            for(int k = 0; k <= up; ++k) {
                if(j - k <= (i - 1) * 9) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k] * k);
                }
            }
        }
    }
    scanf("%d", &T);
    while(T--) {
        sum = 0;
        for(int i = 0; i < 7; ++i) {
            scanf("%d", &x);
            sum += x;
        }
        printf("%d\n", dp[7][sum]);
    }
    return 0;
}

E. 小 Yi 的照片

题意

给出一个 $n\times m$ 的矩阵，按要求生成一个新的矩阵：

1. 对于原矩阵中每一个大小为 $s\times s$（$s$ 为奇数）的子矩阵，若其中心坐标为 $(x,y)$，则新矩阵 $(x,y)$ 处的值等于子矩阵内所有数字的中位数；
2. 其他数字等于原矩阵内的数字。

给定原矩阵以及 $s$，求新矩阵。

数据范围

对于 $75\%$ 的数据，$1\leq n,m\leq100,1\leq s\leq 5$
对于 $100\%$ 的数据，$1\leq n,m\leq500,1\leq s\leq10$，$s$ 为奇数

题解

直接按题意暴力模拟可以通过。这题主要是一个排序，如果刚学完 C 语言的话可能只会冒泡或者选择排序，理论上写冒泡与选择排序无法通过第四组数据，但是我们不卡排序的复杂度，加上洛谷的评测机跑得飞快，所以 $O(n^2)$ 的排序可以通过所有数据。考虑到会用 sort 与不会用 sort 之间存在一定的不公平，所以我们也给出了库函数中的 sort 快速排序的用法示例，减少了手写排序与 debug 的时间。
由于要求标程必须用 C 语言来写，所以下面给出的做法一种是用选择排序，另一种是用计数的方式找到中位数，第一种理论上无法通过第四组但实际上允许通过，第二种理论复杂度可以通过。计数的方式也就是从 $0$ 到 $255$ 统计每个数字出现的次数，用一个变量 $sum$ 从 $0$ 不断往 $255$ 加，一旦 $sum$ 的值大于等于 $\left\lfloor\frac{n}{2}\right\rfloor+1$，则当前的数字就是中位数。

标程

std1.c

#include <stdio.h>
int n, m, s, Index, x;
int num[600][600], ans[600][600], tmp[200];
void Sort(int *num, int n) {
    for(int i = 0; i < n; ++i) {
        Index = i;
        for(int j = i; j < n; ++j) {
            if(num[j] < num[Index]) {
                Index = j;
            }
        }
        x = num[i];
        num[i] = num[Index];
        num[Index] = x;
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            scanf("%d", &num[i][j]);
            ans[i][j] = num[i][j];
        }
    }
    for(int i = 0; i + s - 1 < n; ++i) {
        for(int j = 0; j + s - 1 < m; ++j) {
            Index = 0;
            for(int r = 0; r < s; ++r) {
                for(int c = 0; c < s; ++c) {
                    tmp[Index++] = num[i + r][j + c];
                }
            }
            Sort(tmp, Index);
            ans[i + s / 2][j + s / 2] = tmp[Index / 2];
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

std2.c

#include <stdio.h>
int n, m, s, Index, x;
int num[600][600], ans[600][600], cnt[256], tmp[200];
int findMid(int *num, int n) {
    int sum = 0;
    for(int i = 0; i < 256; ++i) {
        cnt[i] = 0;
    }
    for(int i = 0; i < n; ++i) {
        ++cnt[num[i]];
    }
    for(int i = 0; i < 256; ++i) {
        sum += cnt[i];
        if(sum >= n / 2 + 1) {
            return i;
        }
    }
    return 255;
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            scanf("%d", &num[i][j]);
            ans[i][j] = num[i][j];
        }
    }
    for(int i = 0; i + s - 1 < n; ++i) {
        for(int j = 0; j + s - 1 < m; ++j) {
            Index = 0;
            for(int r = 0; r < s; ++r) {
                for(int c = 0; c < s; ++c) {
                    tmp[Index++] = num[i + r][j + c];
                }
            }
            ans[i + s / 2][j + s / 2] = findMid(tmp, Index);
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

F. 星际穿越

题意

计算在二维平面上的点 $(x_0,y_0)$ 距离椭圆 $\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$ 上的点的最短距离。

数据范围

$1\leq T\leq100$
$0<b\leq a\leq50,-50\leq x_0,y_0\leq50$

题解

由于椭圆在四个象限是对称的，且椭圆上距离 $(x_0,y_0)$ 最近的点一定与该点在同一象限，所以可以将所有点都放到第一象限，计算椭圆 $y=\sqrt{\left(1-\frac{a^2}{x^2}\right)b^2},x\in[0,a]$ 上到点 $(|x_0|,|y_0|)$ 最近的距离，以减少计算量。
这题主要有四种思路：
第一种思路是做一条经过 $(|x_0|,|y_0|)$ 的直线，要求直线与椭圆的交点在椭圆上的切线与直线垂直，对椭圆求导可以得到切线斜率，最后考虑斜率不存在的特殊情况。由于这种做法比较复杂而且最终目的是求解椭圆上点的坐标，计算量大且不如以下方法简便，因此出题人与验题人都没有尝试这种方法。
第二种思路是设椭圆上离 $(|x_0|,|y_0|)$ 最近的点的坐标为 $(x,y)$，则 $(x,y)$ 满足椭圆方程，且要使：

$$\begin{align} dis^2&=\left(x_0-x\right)^2+\left(y_0-y\right)^2\\ &=\left(x_0-x\right)^2+\left(y_0-\sqrt{\left(1-\frac{x^2}{a^2}\right)b^2}\right)^2 \end{align}$$

的值最小，通过对该公式求导令导数等于 $0$ 取极值可以发现，这样很难算。由于答案只要求精确到小数点后两位，所以可以通过在 $[0,a]$ 区间内枚举 $x$ 的值，代入上面的公式取 $dis^2$ 的最小值，就可以得到答案。
第三种思路：由椭圆方程可以得到参数方程：

$$\begin{cases} x=a\cos\theta\\ y=b\sin\theta \end{cases}$$

我们可以将 $\left[0,\frac{\pi}{2}\right]$ 做 $5000$ 等分进行枚举，来计算

$$dis^2=(x_0-\cos\theta)^2+(y_0-\sin\theta)^2$$

的最小值（为了数据的正确性，实际上进行了 $10^5$ 等分，得到准确的数据后，我们才发现实际上只要 $5000$ 等分就可以 $AC$）。
第四种做法是三分，由于给定任意一个第一象限内的点，椭圆上从 $0$ 到 $\frac{\pi}{2}$ 枚举 $\theta$ 的过程中，$dis^2$ 的值总是先减小后增大，满足三分性质，因此可以进行三分，初始的左右端点为 $\left[0,\frac{\pi}{2}\right]$，而后不断将区间三分，取两个分割点 $dis^2$ 值大的那一端缩小区间范围，直到两端距离小于某个值。
最后请用 double 进行计算，用 float 进行计算精度误差很大。

标程

std1.c

#include <stdio.h>
#include <math.h>
int T;
double a, b, xx, yy, ans;
double min(double a, double b) {
    if(a < b) {
        return a;
    }
    return b;
}
double cal(double x1, double y1, double x2, double y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        ans = 1e10;
        scanf("%lf%lf%lf%lf", &a, &b, &xx, &yy);
        xx = fabs(xx);
        yy = fabs(yy);
        for(double x2 = 0; x2 <= a; x2 += 0.00002) {
            ans = min(ans, cal(xx, yy, x2, sqrt((1 - x2 * x2 / a / a) * b * b)));
        }
        printf("%.2lf\n", sqrt(ans));
    }
    return 0;
}

std2.c

#include <stdio.h>
#include <math.h>
int T;
double a, b, xx,yy, ans;
double min(double a, double b) {
    if(a < b) {
        return a;
    }
    return b;
}
double get_dis(double theta) {
    double x = a * cos(theta);
    double y = b * sin(theta);
    return (x - xx) * (x - xx) + (y - yy) * (y - yy);
}
int main() {
    double PI = acos(-1.0);
    scanf("%d", &T);
    while(T--) {
        ans = 1e10;
        scanf("%lf%lf%lf%lf", &a, &b, &xx, &yy);
        xx = fabs(xx);
        yy = fabs(yy);
        for(double theta = 0; theta <= PI / 2; theta += 0.0002) {
            ans = min(ans, get_dis(theta));
        }
        printf("%.2lf\n", sqrt(ans));
    }
    return 0;
}

std3.c

#include <stdio.h>
#include <math.h>
const double eps = 1e-4;
int T;
double high, low, mid1, mid2;
double a, b, xx,yy;
double min(double a, double b) {
    if(a < b) {
        return a;
    }
    return b;
}
double get_dis(double theta) {
    double x = a * cos(theta);
    double y = b * sin(theta);
    return (x - xx) * (x - xx) + (y - yy) * (y - yy);
}
int main() {
    double PI = acos(-1.0);
    scanf("%d", &T);
    while(T--) {
        scanf("%lf%lf%lf%lf", &a, &b, &xx, &yy);
        xx = fabs(xx);
        yy = fabs(yy);
        high = PI / 2;
        low = 0;
        while(high - low > eps) {
            mid1 = (high - low) / 3 + low;
            mid2 = high - (high - low) / 3;
            if(get_dis(mid1) < get_dis(mid2)) {
                high = mid2;
            } else {
                low = mid1;
            }
        }
        printf("%.2lf\n", sqrt(get_dis(high)));
    }
    return 0;
}

G. 送分题 贴代码

题意

用归并排序将一个完全倒序的数组从小到大排好序，输出在排序过程中总共需要进行多少次数字的大小比较操作。

数据范围

对于 $40\%$ 的数据，$1\leq T\leq10^5,~1\leq n\leq10^3$
对于 $80\%$ 的数据，$1\leq T\leq10^6,~1\leq n\leq10^5$
对于 $100\%$ 的数据，$1\leq T\leq10^6,~1\leq n\leq10^7$

题解

延续第一届 $Hello~World$ 算法竞赛的优良传统，送分题一定不是送分题，如果不看数据范围莽一发的话，送分题会一分都不给。
本题利用预处理先算出所有 $f(n)$ 的值存入数组，然后对于每一个输入，直接输出数组中的值，由于预处理的复杂度为 $O(n^2\log n)$，因此最多可以预处理到 $10^3$，得到 $40\%$ 的分数，后面的直接 $WA$ 掉好了，如果想每一组数据都打到 $10^7$ 的话，反而一分都拿不到。
验题人给出了一个小小的优化：

int Merge(int *num, int l, int m, int r) {
    return r - m;
}

因为本题的目的不是排序，而是计数，因此只要计算出交换次数即可，而不必将数组排序，由数组完全倒序可以知道，归并排序的每次归并，比较次数都等于 $r-m$，因此可以减少一趟排序的合并操作，将排序的复杂度从 $O(n\log n)$ 降为 $O(2n)$，但是仍然只能得到 $40\%$ 的分数。
由于这题 $n$ 和 $T$ 的范围极大，因此只有唯一解：找规律 $O(n)$ 打表预处理，存到数组里，对 $T$ 组输入输出对应的答案。用给出的代码先输出 $[1,20]$ 范围的答案，然后找 $n$ 与答案之间的关系，这组数据有两种规律。
出题人发现的规律如下（其中 $bit(x)$ 指的是 $x$ 的二进制表示中数字 $1$ 出现的次数）：

$$f(n)=f(n-1)+bit(n-1)\quad\quad n>1$$

验题人发现的规律是：

$$f(n)=f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+f\left(\left\lfloor\frac{n+1}{2}\right\rfloor\right)+\left\lfloor\frac{n}{2}\right\rfloor\quad\quad n>1$$

标程

std1.c

#include <stdio.h>
const int maxn = 10000000 + 100;
int T, n;
int sum[10000000 + 100];
int bit(int x) {
    int ret = 0;
    for(int i = 0; i < 31; ++i) {
        ret += ((x >> i) & 1);
    }
    return ret;
}
int main() {
    int i;
    sum[1] = 0;
    for(i = 2; i < maxn; ++i) {
        sum[i] = sum[i - 1] + bit(i - 1);
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%d\n", sum[n]);
    }
    return 0;
}

std2.c

#include <stdio.h>
const int maxn = 10000000 + 100;
int T, n;
int sum[10000000 + 100];
int main() {
    int i;
    sum[1] = 0;
    for(i = 2; i < maxn; ++i) {
        sum[i] = sum[i / 2] + sum[(i + 1) / 2] + i / 2;
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%d\n", sum[n]);
    }
    return 0;
}

H. Hack 双哈希

题意

给出了字符串 $hash$ 的代码以及一个字符串，要求找到另一个字符串，该字符串的哈希值与给定字符串相等，要求找到的字符串长度不超过 $100000$，且都为小写字母。

题解

输出原字符串的话直接给 $WA$，如果直接输出原串可以得分的话，这题就是真正的送分题了。
如果按长度和字典序暴力枚举字符串的话，按计算机 $1$ 秒做 $10^8$ 次计算的速度估算，大概要跑 $1933$ 年才能得到长度最短，字典序最小的字符串。
观察代码可以发现，Hash 函数调用了 Hash1 与 Hash2 函数，由于 Hash1 得到的数字最长只有 $9$ 位，Hash2 得到的数字最长大概率只有 $9$ 位（有 $\frac{7}{1000000007}$ 的概率可能为 $10$ 位），因此将 Hash1 的返回值乘上 $10^9$ 再加 Hash2 的返回值，可以认为这两个哈希值是独立的。
题目给出了提示，Hash2 函数是可以进行逆运算的，因此可以通过哈希值 $x$ 计算得到一个字符串，使得该字符串的哈希值恰好等于 $x$。通过观察可以发现，Hash2 实际上是将字符串看作 $26$ 进制的数字，转化为 $10$ 进制的数字后对 $10^9+7$ 取余，其中 a~z 分别对应 $10$ 进制数的 $[1,26]$，但是没有字母对应的是 $0$，如 a 对应 $1$，z 对应 $26$，而下一个 $26$ 进制数 aa 的哈希值为 $1\times26^1+1\times26^0=27$，正好等于 $Hash2($ z$)+1$。
反推可以得到，从哈希值逆运算得到字符串的算法为：先对 $26$ 取余，若余数等于 $0$，则当前位等于 z，并将数字减去 $26$，否则当前位的字母等于余数对应的字母（如 $1$ 对应 a，$2$ 对应 b，以此类推），不断对 $26$ 取余再除以 $26$ 下取整，得到一个字符串，方法类似于将 $10$ 进制数转化为 $16$ 进制数。
将题目给定的字符串作为 Hash2 的参数得到哈希值 $291377266$，因此对 $10^9+7$ 取余之前的哈希值可能为 $x\times(10^9+7)+291377266$，其中 $x$ 为自然数。题给字符串作为 Hash1 的参数得到哈希值 $752542039$，因此可以通过枚举 $x$ 所有可能的值，逆运算得到一个字符串，将字符串代入到 Hash1 中，只要返回值等于 $752542039$，该字符串就是答案。
在不爆 long long 的情况下，$x$ 可能的取值范围大约为 $[0,9\times10^9]$，$9\times10^9$ 个字符串中存在一个用 Hash1 得到的哈希值与 $752542039$ 相等的概率还是很大的（事实证明必然存在），此时字符串长度必然不超过 $18$。用以下代码大概跑 $170$ 秒可以跑出结果：dwdeoqlmczimq，该字符串对应的 Hash2 对 $10^9+7$ 取余前的值为 $466728838558479111$，题目时限为 $1$ 秒，所以本地跑出这个字符串，直接 printf 得分。
以上方法仅供参考，如果有大神可以给出 $O(1)$ 的算法，请给出并收下我的膝盖。

本地暴力跑代码

#include <stdio.h>
int Hash1(char *str) {
    int ret = 0;
    for(int i = 0; str[i] != '\0'; ++i) {
        if((i & 1) == 0) {
            ret ^= ((ret << 7) ^ str[i] ^ (ret >> 3));
        } else {
            ret ^= (~((ret << 11) ^ str[i] ^ (ret >> 5)));
        }
    }
    return ret & 0x2FFFFFFF;
}
int Hash2(char *str) {
    int ret = 0;
    int MOD = 1000000007;
    for(int i = 0; str[i] != '\0'; ++i) {
        ret = ((long long)ret * 26 + (str[i] - 'a' + 1)) % MOD;
    }
    return ret;
}
void Reverse(char *str, int len) {
    char ch;
    for(int i = 0; i < len / 2; ++i) {
        ch = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = ch;
    }
}
void num2str(long long num, char *str) {
    int len = 0;
    while(num != 0) {
        if(num % 26 == 0) {
            str[len++] = 'z';
            num -= 26;
        } else {
            str[len++] = 'a' + num % 26 - 1;
        }
        num /= 26;
    }
    str[len] = '\0';
    Reverse(str, len);
}
int main() {
    char str[20];
    for(long long i = 0; i <= 9000000000LL; ++i) {
        long long x = 291377266 + 1000000007 * i;
        num2str(x, str);
        if(Hash1(str) == 752542039) {
            printf("%s\n", str);
            break;
        }
    }
    return 0;
}

标程

#include <stdio.h>
int main() {
    printf("dwdeoqlmczimq\n");
    return 0;
}