UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204865#3631. 解决难题smallstone1001450ms1972kbC++111.5kb2024-06-10 11:45:182024-06-10 12:07:06

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// using LL = __int128
#define mod 1000000007ll
ll a[333][333], n;
ll bigmul(ll a, ll b, ll m)
{
	unsigned long long c =
		(unsigned long long)a * b -
		(unsigned long long)((long double)a / m * b + 0.5L) * m;
	return (c + m) % m;
}
ll qpow(ll x, ll y)
{
	ll ans = 1, res = x % mod;
	while (y)
	{
		if (y & 1)
			ans = bigmul(ans, res, mod);
		res = bigmul(res, res, mod);
		y >>= 1;
	}
	return ans;
}
ll inv(ll x)
{
	return qpow(x, mod - 2);
}
void solve()
{
	for (int i = 1; i <= n; i++)
	{
		int p = i;
		for (int j = 1; j <= n; j++)
		{
			if (j < i && a[j][j])
				continue;
			if (a[j][i] > a[p][i])
				p = j;
		}
		for (int j = 1; j <= n + 1; j++)
			swap(a[i][j], a[p][j]);
		if (!a[i][i])
			continue;
		for (int j = 1; j <= n; j++)
			if (j != i)
			{
				ll f = a[j][i] * inv(a[i][i]) % mod;
				for (int k = 1; k <= n + 1; k++)
				{
					a[j][k] = a[j][k] - f * a[i][k] % mod;
					a[j][k] = (a[j][k] % mod + mod) % mod;
				}
			}
	}
	for(int i = 1 ; i <= n ; i++){
		a[i][n + 1] = a[i][n + 1] * inv(a[i][i]) % mod;
		printf("%lld ", a[i][n + 1]);
	}
}
int main()
{
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%1lld", &a[j][i]);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i][n + 1]);
		a[i][n + 1] %= mod;
		a[i][n + 1] = mod - a[i][n + 1];
		a[i][n + 1] %= mod;
	}
	solve();
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1200kb

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: 1204kb

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: 1204kb

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: 208ms
memory: 1972kb

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: 203ms
memory: 1968kb

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: 205ms
memory: 1972kb

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: 209ms
memory: 1968kb

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: 207ms
memory: 1968kb

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: 210ms
memory: 1972kb

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: 208ms
memory: 1968kb

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