ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#204846 | #3631. 解决难题 | lsr | 100 | 608ms | 1992kb | C++11 | 1.4kb | 2024-06-10 10:06:36 | 2024-06-10 12:03:18 |
answer
#include <bits/stdc++.h>
using namespace std;
#define QwQ3301AwA return 0
#define ll long long
const int N = 305;
const int mod = 1e9 + 7;
int n;
int s[N][N], a[N];
int w[N][N];
int ksm(int a, int b) {
int ans = 1;
for (; b; b >>= 1, a = 1ll * a * a % mod) {
if (b & 1) ans = 1ll * ans * a % mod;
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
string t;
cin >> t;
for (int j = 1; j <= n; j++) {
s[i][j] = t[j - 1] - '0';
}
}
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = s[j][i];
}
w[i][n + 1] = (mod - a[i]) % mod;
}
for (int i = 1; i <= n; i++) {
int id = i;
for (int j = i + 1; j <= n; j++) {
if (w[j][i]) id = j;
}
if (id != i) swap(w[i], w[id]);
int iv = ksm(w[i][i], mod - 2);
for (int j = 1; j <= n + 1; j++) w[i][j] = 1ll * w[i][j] * iv % mod;
for (int j = 1; j <= n; j++) {
if (i == j) continue;
int xs = w[j][i];
for (int k = 1; k <= n + 1; k++) {
w[j][k] = (w[j][k] - 1ll * xs * w[i][k] % mod + mod) % mod;
}
}
}
for (int i = 1; i <= n; i++) cout << w[i][n + 1] << ' ';
QwQ3301AwA;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 1280kb
input:
5 76703 98327 73227 92255 86574 999999955 999999969 999999986 999999982 999999973
output:
0 3 0 1 2
result:
ok single line: '0 3 0 1 2 '
Test #2:
score: 10
Accepted
time: 0ms
memory: 1288kb
input:
6 422776 414954 155320 199876 991820 249380 999999971 999999942 999999963 999999944 999999971 999999...
output:
0 1 2 3 3 0
result:
ok single line: '0 1 2 3 3 0 '
Test #3:
score: 10
Accepted
time: 0ms
memory: 1284kb
input:
7 8466030 1242063 9970648 8406710 6727521 3812850 6818000 999999949 999999932 999999967 999999975 99...
output:
1 2 3 0 0 3 2
result:
ok single line: '1 2 3 0 0 3 2 '
Test #4:
score: 10
Accepted
time: 90ms
memory: 1988kb
input:
300 270000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
916258358 519022538 821314397 887968260 11163141 313697293 687278761 469796877 984340226 751985575 5...
result:
ok single line: '916258358 519022538 821314397 ... 331722994 308740977 758811862 '
Test #5:
score: 10
Accepted
time: 86ms
memory: 1992kb
input:
300 670000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
793590813 38968613 380775900 856812394 892644411 739342894 618361240 909158937 596399756 765250805 3...
result:
ok single line: '793590813 38968613 380775900 8... 600870385 829088743 827827874 '
Test #6:
score: 10
Accepted
time: 85ms
memory: 1992kb
input:
300 260000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
260857797 558914696 641474878 530689259 774125674 873816490 135582984 53553722 208459287 483548768 8...
result:
ok single line: '260857797 558914696 641474878 ... 873813040 349436502 601876619 '
Test #7:
score: 10
Accepted
time: 86ms
memory: 1988kb
input:
300 542128399337590285552625503935250783437069735052009124583459108286630823938623650996978703141295...
output:
459797728 372681007 711682710 189156773 637377863 425217164 697243107 969129956 342783347 843862464 ...
result:
ok single line: '459797728 372681007 711682710 ... 945919047 546146588 650580996 '
Test #8:
score: 10
Accepted
time: 86ms
memory: 1988kb
input:
300 343453698687744797543345812953303350530512599745228777654167066084273997667944678773815747388110...
output:
337130183 892627090 271144213 863033645 813826393 145830026 919497590 408492009 659875616 857127694 ...
result:
ok single line: '337130183 892627090 271144213 ...9 215066431 66494347 424629741 '
Test #9:
score: 10
Accepted
time: 88ms
memory: 1988kb
input:
300 773493559344634369215007470620961968422951355377925074753917769102332126548041118014733383081237...
output:
509429906 707540433 826810458 540705775 986479660 571475627 440514599 552886801 271935147 575425656 ...
result:
ok single line: '509429906 707540433 826810458 ... 193041818 291874845 493645754 '
Test #10:
score: 10
Accepted
time: 86ms
memory: 1988kb
input:
300 670162159026137251715327745422913995527399141028480083023288273026330075072367299393258107821374...
output:
681729629 227486508 91304693 509549909 867960922 705949224 662769082 287216122 589027416 883658154 6...
result:
ok single line: '681729629 227486508 91304693 5... 757156478 107189872 267694498 '
Extra Test:
score: 0
Extra Test Passed