#YDRG004C. 不妨学一学《深入理解计算机系统》
不妨学一学《深入理解计算机系统》
题目背景
小芙和小希某天刚考完 CSAPP(深入理解计算机系统)这门课的期末,便凑在一次开始对答案。我们都知道,考完试忙着对答案往往会有“惊喜”降临。不出所料,他们发现了这样一个惊喜——
题目描述
他们依稀记得,考场上有一道题是这样的:
给定两个长度均为 的二进制串,请你计算两者相乘的结果,且将结果保留为 位。
但是,他们忘记这两个二进制串是在做有符号二进制数乘法,还是无符号二进制数乘法了。
小芙是按有符号乘法做的,而小希是按照无符号乘法做的——这两者显然有着天壤之别。以下是一些简单介绍:
有符号数的二进制表示是该数的补码,最高位默认是符号位。
举个例子来讲,
11101001
和11010101
在无符号乘法时,分别表示 和 。 答案为1100 0001 1101 1101(2)=49629(10)
。而在有符号乘法时,两者分别表示 和 。 答案为
0000 0011 1101 1101(2)=989(10)
。
在发现这一事实后,悲观的小芙认为:
“完了,这下咱俩至少一个要完蛋了!”
而乐观的小希则觉得:
“不一定,万一两个答案有重合的地方呢?”
到最后,两人争执不下,两人只能打了一个赌:
我们默认两个人算的答案在各自的算法下都是计算正确的。设两人答案(答案
指的是长度为 的结果二进制串)里相同的位数为 ,不同的位数为 。显然 。那么:
- 当 时,小芙要请小希吃饭。
- 当 时,小希要请小芙吃饭。
现在,给定你两个长度均为 的 串,请你计算出谁要请吃饭。
注意,我们认为结果一定是 位,这可能需要补足额外的前导 0 。
输入格式
由于输入量过大,为了防止输入导致的额外耗时,采取种子生成的方式生成输入数据。
第 行共一个整数 ,表示单个测试点的数据组数。
第 行,每行包含 个种子 。其中 为 01 串的长度,详情请见题目描述。 为生成参数。设 int
类型数组 sA[], sB[]
分别表示需要做乘法两个 01 串,则具体的生成逻辑如下:
const int N = 3000010 ;
int k, a, b, c, d ;
int sA[N], sB[N] ;
int main(){
cin >> k >> a >> b >> c >> d ;
for (int i = 1 ; i <= k ; ++ i)
sA[i] = ((1ll * sA[i - 1] * a + b) % c) ^ d ;
for (int i = 1 ; i <= k ; ++ i)
sB[i] = ((1ll * sB[i - 1] * d + c) % b) ^ a ;
for (int i = 1 ; i <= k ; ++ i){
sA[i] &= 1 ;
sB[i] &= 1 ;
}
return 0 ;
}
输出格式
输出共 行。对于每一组询问,设小芙、小希两人答案里相同的位数为 ,不同的位数为 。显然 。那么:
- 当 时,小芙要请小希吃饭,此时输出一行共一个字符串
Frieren
。 - 当 时,小希要请小芙吃饭,此时输出一行共一个字符串
Himmel
。
样例 #1
输入样例
1
4 12 15 17 8
输出样例
Frieren
样例 #1 解释
当输入为 4 12 15 17 8
时,两个字符串分别为 1000
和 0100
。当将二者视为有符号数时,两者分别代表十进制下的 和 ,相乘得到 -32(10)=00100000(2)
。当将二者视为无符号时,两者分别代表十进制下的 和 ,相乘得到 32(10)=00100000(2)
。
因此,相同的位数 ,不同的位数 ,,小芙要请小希吃饭,因此输出一行一个字符串 Frieren
。
样例 #2
输入样例
1
4098 13354 2016 17789 3213
输出样例
Frieren
数据范围
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于全部 的数据,$k\leq 3\times 10^6,0< a,b,c,d\le 2\times 10^9,t\leq 5$。