题目链接:uva 1564 - Widget Factory
题目大意:n种零件,m次工作日程,零件序号从1到n,给出m次工作日程的信息,x,s,e,表示生产了x个零件,从星期s开始到星期e(有可能是多个星期),然后给出生产的x个零件的序号。求每个零件被生产需要多少天(保证在3到10天)
解题思路:因为不能确定每个工作日程具体生产了几天,所以对应列出的方程均为线性模方程(模7),所以在高斯消元的过程中遇到除法要转换成乘上逆元。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 305;
const int maxd = 7;
const char day[maxd][maxd] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
typedef long long ll;
typedef ll Mat[maxn][maxn];
int N, M;
Mat A;
int solve (char *s, char *e) {
int p = 0;
while (strcmp(s, day[p])) p++;
int q = p;
while (strcmp(e, day[q])) q = (q + 1) % maxd;
return (q - p + 8) % maxd;
}
void init () {
int n, x;
char s[maxn], e[maxn];
memset(A, 0, sizeof(A));
for (int i = 0; i < M; i++) {
scanf("%d%s%s", &n, s, e);
for (int j = 0; j < n; j++) {
scanf("%d", &x);
A[i][x-1] = (A[i][x-1] + 1) % maxd;
}
A[i][N] = solve(s, e);
}
}
ll pow_mod(ll x, int n, ll mod) {
ll ret = 1;
while (n) {
if (n&1)
ret = ret * x % mod;
x = x * x % mod;
n >>= 1;
}
return ret;
}
ll inv (ll k) {
return pow_mod(k, maxd-2, maxd);
}
int gauss_elimin (int n, int m) {
int i = 0, j = 0;
while (i < m && j < n) {
int r = i;
for (int k = i; k < m; k++) {
if (A[k][j]) {
r = k;
break;
}
}
if (r != i) {
for (int k = 0; k <= n; k++)
swap(A[i][k], A[r][k]);
}
if (A[i][j] == 0) {
j++;
continue;
}
for (int k = 0; k < m; k++) {
if (A[k][j] == 0 || i == k)
continue;
ll f = A[k][j] * inv(A[i][j]) % maxd;
for (int t = j; t <= n; t++)
A[k][t] = ((A[k][t] - f * A[i][t]) % maxd + maxd) % maxd;
}
i++;
}
for (int k = i; k < m; k++)
if (A[k][n])
return 0;
if (i < n)
return 2;
for (int k = 0; k < n; k++) {
A[k][n] = A[k][n] * inv(A[k][k]) % maxd;
if (A[k][n] < 3)
A[k][n] += maxd;
printf("%lld%c", A[k][n], k == n-1 ? '\n' : ' ');
}
return 1;
}
int main () {
while (~scanf("%d%d", &N, &M) && N) {
init();
int type = gauss_elimin(N, M);
if (type == 0)
printf("Inconsistent data.\n");
else if (type == 2)
printf("Multiple solutions.\n");
}
return 0;
}
分享到:
相关推荐
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
组合数学- 组合数取模- 逆元与递推打表.rar
算法-数论- 逆元.rar
算法-数论- 逆元与同余式定理.rar
c/c++相关代码(cpp),乘法逆元有关模板整合(附有注释),顺便整合了了阶乘逆元,以及排列组合计算和Lucas的模板代码。
本程序可进行仿射加密和求解逆元的操作。 1-仿射加密,2-求逆元
群判定,逆元,元素的阶 #include using namespace std; #define N 10000 //对四元群运算函数的定义 char ysuan(char a,char b) { char arr[4]={'a','b','c','e'}; int i=0,j=0; if(a==b) { return arr[3]; }...
3. 高斯消元 4. 组合计数 加法原理和乘法原理 排列数和组合数 组合数的性质 二项式定理 5. 简单容斥原理 各集合的交集 容斥原理 6. 概率与数学期望(经典例题: [蓝桥杯 2022 国 B] 故障、[国家集训队] ...
扩展欧几里得算法求逆元
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
简单讲解用辗转相除法计算乘法逆元,用于密码学加密,附C语言实现算法(对正整数运算)
数论
网络安全课程上机作业,用matlab编写的求解乘法逆元代码,如果有什么问题请留言。
算法-乘法逆元(洛谷-P3811)(包含源程序).rar
加密解密的基础,扩展欧几里得算法(辗转相除法)
用C语言简单实现乘法逆元计算的代码(!只能计算正整数)
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
关于 线性求逆元 算法的代码,自己写的,和大家分享,希望大家能多多指教
用递归实现的求逆元的代码,使用中的算法是扩展的欧几里得算法。输入本元和模数,得到乘法逆元。
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。