QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474429#2568. Mountainslichenyu_acAC ✓15ms22928kbC++141.2kb2024-07-12 18:05:162024-07-12 18:05:17

Judging History

你现在查看的是最新测评结果

  • [2024-07-12 18:05:17]
  • 评测
  • 测评结果:AC
  • 用时:15ms
  • 内存:22928kb
  • [2024-07-12 18:05:16]
  • 提交

answer

#include<bits/stdc++.h>
#define ing long long 
typedef long long ll;
using namespace std;
const int N=2e3+10,M=1e6+10,mod=1e9+7;

ll power(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}

ll n,m,K;
ll A[N][N],f[M],incf[M];
void init(int len){
	f[0]=1;
	for(int i=1;i<=len;i++)f[i]=f[i-1]*i%mod;
	incf[len]=power(f[len],mod-2);
	for(int i=len-1;i>=0;i--)incf[i]=incf[i+1]*(i+1)%mod;
}

ll C(ll a,ll b){
	if(a<b)return 0;
	return f[a]*incf[b]%mod*incf[a-b]%mod;
}

ll Guess(){
	ll op=1,ans=1;
	for(int i=1;i<=K;i++){
		int pos=i;
		for(int j=i+1;j<=K;j++)
			if(A[j][i]>A[pos][i])pos=j;
		if(i!=pos)op=-op,swap(A[i],A[pos]);
		if(!A[i][i])return 0;
		for(int j=1;j<=K;j++){
			if(j==i)continue;
			ll tmp=A[j][i]*power(A[i][i],mod-2)%mod;
			for(int k=1;k<=K;k++)
				A[j][k]=(A[j][k]-tmp*A[i][k]%mod+mod)%mod;
		}
		ans=ans*A[i][i]%mod;
		ll tmp=power(A[i][i],mod-2);
		for(int j=1;j<=K;j++)A[i][j]=A[i][j]*tmp%mod;
	}
	return (ans*op%mod+mod)%mod;
}

signed main(){
	init(M-1);
	scanf("%lld%lld%lld",&n,&m,&K);
	for(int i=1;i<=K;i++)
		for(int j=1;j<=K;j++){
			ll x=n+(j-i),y=m-(j-i);
			if(x>=0&&y>=0&&x<N&&y<N)A[i][j]=C(x+y,x);
		}
	printf("%lld\n",Guess());
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 21436kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 12ms
memory: 20232kb

input:

2 2 2

output:

20

result:

ok 1 number(s): "20"

Test #3:

score: 0
Accepted
time: 7ms
memory: 20284kb

input:

2 3 4

output:

490

result:

ok 1 number(s): "490"

Test #4:

score: 0
Accepted
time: 7ms
memory: 19876kb

input:

1 2 8

output:

45

result:

ok 1 number(s): "45"

Test #5:

score: 0
Accepted
time: 7ms
memory: 21172kb

input:

1 10 2

output:

66

result:

ok 1 number(s): "66"

Test #6:

score: 0
Accepted
time: 3ms
memory: 21100kb

input:

9 5 7

output:

371850968

result:

ok 1 number(s): "371850968"

Test #7:

score: 0
Accepted
time: 7ms
memory: 20400kb

input:

3 3 1

output:

20

result:

ok 1 number(s): "20"

Test #8:

score: 0
Accepted
time: 7ms
memory: 21704kb

input:

7 7 9

output:

166345303

result:

ok 1 number(s): "166345303"

Test #9:

score: 0
Accepted
time: 11ms
memory: 20508kb

input:

25 15 25

output:

850087558

result:

ok 1 number(s): "850087558"

Test #10:

score: 0
Accepted
time: 8ms
memory: 21632kb

input:

45 59 71

output:

659153227

result:

ok 1 number(s): "659153227"

Test #11:

score: 0
Accepted
time: 11ms
memory: 21928kb

input:

73 3 25

output:

683124269

result:

ok 1 number(s): "683124269"

Test #12:

score: 0
Accepted
time: 9ms
memory: 22056kb

input:

1 48 78

output:

446896916

result:

ok 1 number(s): "446896916"

Test #13:

score: 0
Accepted
time: 7ms
memory: 21256kb

input:

25 100 32

output:

966287506

result:

ok 1 number(s): "966287506"

Test #14:

score: 0
Accepted
time: 8ms
memory: 21728kb

input:

85 64 40

output:

125679545

result:

ok 1 number(s): "125679545"

Test #15:

score: 0
Accepted
time: 7ms
memory: 21104kb

input:

5 9 94

output:

620471576

result:

ok 1 number(s): "620471576"

Test #16:

score: 0
Accepted
time: 12ms
memory: 21728kb

input:

33 57 40

output:

637315057

result:

ok 1 number(s): "637315057"

Test #17:

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

input:

61 6 97

output:

362472796

result:

ok 1 number(s): "362472796"

Test #18:

score: 0
Accepted
time: 12ms
memory: 20628kb

input:

85 50 51

output:

192099209

result:

ok 1 number(s): "192099209"

Test #19:

score: 0
Accepted
time: 12ms
memory: 21752kb

input:

96 54 59

output:

714762612

result:

ok 1 number(s): "714762612"

Test #20:

score: 0
Accepted
time: 11ms
memory: 20340kb

input:

20 99 12

output:

772155662

result:

ok 1 number(s): "772155662"

Test #21:

score: 0
Accepted
time: 6ms
memory: 22224kb

input:

48 39 62

output:

670046604

result:

ok 1 number(s): "670046604"

Test #22:

score: 0
Accepted
time: 5ms
memory: 21148kb

input:

76 83 16

output:

976820079

result:

ok 1 number(s): "976820079"

Test #23:

score: 0
Accepted
time: 4ms
memory: 22044kb

input:

96 36 61

output:

20854557

result:

ok 1 number(s): "20854557"

Test #24:

score: 0
Accepted
time: 13ms
memory: 21852kb

input:

18 40 77

output:

261684871

result:

ok 1 number(s): "261684871"

Test #25:

score: 0
Accepted
time: 12ms
memory: 20776kb

input:

42 84 26

output:

458573307

result:

ok 1 number(s): "458573307"

Test #26:

score: 0
Accepted
time: 9ms
memory: 21200kb

input:

71 25 80

output:

875902815

result:

ok 1 number(s): "875902815"

Test #27:

score: 0
Accepted
time: 7ms
memory: 20120kb

input:

95 73 26

output:

922299967

result:

ok 1 number(s): "922299967"

Test #28:

score: 0
Accepted
time: 13ms
memory: 21148kb

input:

19 17 83

output:

494148696

result:

ok 1 number(s): "494148696"

Test #29:

score: 0
Accepted
time: 15ms
memory: 22796kb

input:

100 100 100

output:

192912055

result:

ok 1 number(s): "192912055"

Test #30:

score: 0
Accepted
time: 11ms
memory: 21836kb

input:

100 98 99

output:

412293529

result:

ok 1 number(s): "412293529"