2.2 高斯消元法求解模线性方程组

模线性方程组是形式为的方程组，其中，aij、bi和p为整数（1≤i,j≤n）；求x1,x2,…,xn的模p整数解。

消元时，如果aki%aii≠0（1≤k≤n），则将aki所在行乘以LCM(aki,aii)/aki，这样，aki就转变为它们的最小公倍数LCM(aki,aii)；因为是模线性方程组求解运算，所以在矩阵初等行变换后，还要对变换的行再进行模运算，为回代求解时使用逆元。

例如，模线性方程组，则是对应的增广矩阵。通过矩阵初等行变换，把增广矩阵转换为阶梯矩阵的过程如下。

第一步，。首先，将第一行和第三行交换，使a11的绝对值最大，其次，第2行和第3行分别乘以LCM(a21,a11)/a21和LCM(a31,a11)/a31，即，第2行的元素乘以2，第3行的元素乘以4；再次，第1行乘以LCM(a21,a11)/a11和LCM(a31,a11)/a11，并取负，加到第2行和第3行；由于是模线性方程组求解运算，最后，对第2行和第3行的元素除以5取余。

第二步，，得到阶梯矩阵。同样，首先，将第二行与第三行交换，使a22的绝对值最大，其次，第3行乘以LCM(a32,a22)/a32，即乘以4；再次，第2行乘以LCM(a32,a22)/a22，并取负，加到第3行；最后，对第3行的元素除以5取余。

阶梯矩阵对应的模线性方程组为，则x1、x2和x3的解为：由(1)得，x1=1；由(2)得，x2=2；由(3)得，x3=4。

注意：在解模线性方程组时，当有唯一解时，需要对每个方程的唯一解不断循环取模判断，直到找出能整除的为止。

模线性方程组求解的程序模板如下。

题目2.2.1和2.2.2是应用高斯消元法求解模线性方程组的范例。

【2.2.1 Widget Factory】

部件厂生产若干种不同类型的部件。每个部件由技术熟练的技术工人精心制造。制造一个部件所需的时间取决于它的类型：制造简单的部件只需要3天，但制造最复杂的部件可能需要长达9天。

工厂目前正处于完全混乱的状态。最近，工厂被一个新老板收购，而新老板几乎解雇了所有人。新工人对制造部件一无所知，也没有人记得制造每种不同的部件需要多少天。当一个客户预订了一批部件，而工厂却不能告诉客户制造所需的部件需要多少天，是非常尴尬的。幸运的是，每个技术工人何时开始为工厂工作，何时被工厂解雇，以及他制造了什么类型的部件，工厂都有记录。但问题是，工厂的记录没有明确给出技术工人开始工作和离职的确切日期，只给出一周中的某一天；而且，这方面的资料只在某些情况下是有帮助的：例如，如果一个技术工人在一个周二开始工作，制造了1个类型41的部件，并在周五被解雇，那么我们就知道，制造1个类型41部件需要4天。请根据这些记录（如果可能）计算制造不同类型的部件需要的天数。

输入

输入给出若干测试用例，每个测试用例的第一行给出两个整数：n(1≤n≤300)，不同类型部件的种类数；m(1≤m≤300)，记录的数目。这一行的后面给出m条记录的描述，每条记录描述由两行组成，第一行给出该技术工人制造的部件的总数k(1≤k≤10000)，然后给出他是在星期几开始工作的，又是在星期几被解雇的。星期几用字符串“MON”“TUE”“WED”“THU”“FRI”“SAT”和“SUN”给出。第二行给出用空格分开的k个整数，这些数在1和n之间，表示该技术工人制造的不同类型的部件。例如，下面的两行表示一个技术工人在周三开始为工厂干活，制造了1个类型13的部件、1个类型18的部件、1个类型1的部件和1个类型13的部件，最后在周日被解雇。

4 WED SUN

13 18 1 13

技术工人一周工作7天，在第一天和最后一天之间，他们每天都在工厂里工作。

输入以测试用例n=m=0结束。

注意：对于海量输入，建议使用scanf，以避免超时。

输出

对于每个测试用例，输出一行，给出由空格分隔的n个整数：制造不同类型的部件所需要的天数。在第一个数字之前以及最后一个数字之后，没有空格，而在两个数字之间有一个空格。如果有一个以上的解，则输出“Multiple solutions.”（不带引号）；如果确定相应于输入无解，则输出“Inconsistent data.”（不带引号）。

试题来源：ACM Central Europe 2005

在线测试：POJ 2947，UVA 3529

试题解析

本题题意：有n种不同类型的部件，每种部件的制造时间是3～9天，但由于原来的技术工人被解雇了，因此不知道制造每种不同的部件需要多少天。每个技术工人何时开始为工厂工作，何时被工厂解雇，以及他制造了什么类型的部件，工厂都有记录，但只给出了是星期几，并不知道具体的时间；在技术工人工作的这段时间中，制造了k个部件，并给出k个部件的编号。基于这些信息，要确定每种部件的制造天数。

对于每条记录，建立一个方程，m条记录就有m个方程。n种不同类型部件，编号为0～n-1，xi(0≤i≤n-1)表示第i种部件的加工时间，a[i][j]表示在第i个方程中编号为j的部件被制造的个数，a[i][n]表示在第i个方程中制造完所用部件所需的时间，由于不知道开始和结束时间是在第几个星期，因此a[i][n]是进行模7运算的结果，例如TUE到MON运算结果就是6。模线性方程组如下：

若出现自由元，则表明有多解；若系数矩阵某一行向量为0，而增广矩阵对应的变量值非为0，则无解。

注意：如果有解，最终答案应从0～6映射至3～9，因为制造一个部件所需的时间为3～9天。

参考程序

【2.2.2 SETI】

近年来，为了了解遥远星系中的文明可能在试图告诉我们什么，科学家们在监听来自太空的电磁无线电信号方面做了许多的工作。有一个信号源让宇宙空间科学家们特别感兴趣。

最近，人们发现，如果每条信息被定义为一个整数序列a0,a1,…,an-1，函数的值0≤f(k)≤26，其中1≤k≤n,n是传输消息的长度，ai是整数，且0≤ai<p,p是一个大于n也大于26的素数，这个数字不会超过30000。

语言学家将这些信息转换为由英文字母组成的字符串，以便在试图解释其含义时能更容易地处理它们。转换过程很简单，用字母a..z表示f(k)的计算值，对于1..26，1=a，2=b，以此类推；0则被转换成星号（*）。在转换信息时，语言学家使k从1到n进行循环，计算f(k)，并在表示信息的字符串末尾加上f(k)的值对应的字符。

然而，反向转换过程对于语言学家来说太复杂了。因此，请编写一个程序，将一组字符串转换成相应的数字序列。

输入

在输入的第一行给出一个正整数N，表示后面给出的测试用例数。每个测试用例一行，首先给出在字符串转换过程中使用的p的值，然后给出要被转换的字符串。字符串由小写字母a～z以及星号（*）组成。字符串长度不得超过70。

输出

对于每个要转换的字符串，输出一行对应的整数列表，整数之间用空格分隔，整数按i的升序排列。

试题来源：ACM Northwestern Europe 2004

在线测试：POJ 2065，UVA 3131

试题解析

本题输入给出若干个测试用例，每个测试用例给出一个素数p，以及一个字符串，字符串的长度为n，字符串由小写字母a～z以及星号（*）组成，其中每个字符对应一个数值，小写字母a～z对应1～26，“*”对应0，第i个字符对应的数值是f(i)的计算值。有如下的模线性方程组：

本题要求求解a0,a1,…,an-1。

上述模线性方程组的解是唯一确定的，不需要判断无解和无穷解的情况，同时需要使用快速幂取余计算i^(n-1) modp。

参考程序