2012-10-25 08:38:14Morris
[ZJ][逆元] a545. Stressful
內容 ：
在 這充滿學測考生的圖書館中，每個人都感受到莫大的壓力，但由於每個人的實力值不同，所以感受到的壓力值也不同，因此便有一種量化壓力值的算法，來求得每一 位考生所感受到的壓力，這種算法便是除了自己以外的實力值通通相乘起來，便能得到該名考生在圖書館中所感受到的壓力值。但對於準備學測的考生來說，沒有辦 法花時間來一一計算自己的壓力值，因此，你被要求編寫一段程式來求得每位考生所感受到的壓力值為何。
此處該圖書館為一矩陣，且由於準備學測的考生眾多，並沒有任何位置被空置下來。
輸入說明
：
輸入第一行包含兩正整數m,n(0<m,n<=103)。
接下來m行，每行有n個正整數Vij，代表該位置上考生的實力值。
接下來一行包含一個正整數q(0<q<=104)，代表接下來會有q筆詢問。
接下來q行各包含兩個正整數x,y(0<x<=m,0,<y<=n)。
測試資料以兩個零代表輸入結束。
任何數據皆能以long long(64 bits)儲存。
輸出說明
：
對於每一筆詢問求出在位置(x,y)的考生所感受到的壓力值，由於壓力值可能非常大請輸出該名考生壓力值對於 100000007 的餘數即可。
範例輸入 ：
2 3 1 2 3 4 5 6 1 1 2 0 0
範例輸出 ：
360
提示
：
背景知識：
範例測資如下
Index | 1 | 2 | 3 |
1 | 1 | 2 ◎ | 3 |
2 | 4 | 5 | 6 |
詢問的考生如◎標記處，則其壓力值為其餘所有考生實力值相乘(1*3*4*5*6)，即為範例輸出之360。
出處
：
這題一定要優化輸入。
逆元的求法可以使用費馬小定理 (因為 1,0000,0007 是個質數)。
或者使用 gcd 的方法。
#include <stdio.h>
#include <stdlib.h>
#define mod 100000007LL
#define LL long long
int A[1005][1005];
LL inv(LL a) {
LL d = mod, x = 0, s = 1, q, r, t;
while(a) {
q = d / a, r = d % a;
d = a, a = r;
t = x - q * s, x = s, s = t;
}
if (d != 1) return -1;
return (x + mod) % mod;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, m, q, i, j;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0) break;
LL tot = 1, tmp;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
ReadInt(&A[i][j]);
if(A[i][j] >= mod)
A[i][j] %= mod;
tot *= A[i][j];
if(tot >= mod)
tot %= mod;
}
}
tot = (tot+mod)%mod;
scanf("%d", &q);
while(q--) {
scanf("%d %d", &i, &j), i--, j--;
tmp = inv(A[i][j])*tot;
if(tmp >= mod)
tmp %= mod;
printf("%lld\n", tmp);
}
}
return 0;
}