QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474416#2568. Mountainslichenyu_acWA 11ms21044kbC++141.4kb2024-07-12 17:57:062024-07-12 17:57:06

Judging History

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

  • [2024-07-12 17:57:06]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:21044kb
  • [2024-07-12 17:57:06]
  • 提交

answer

#include<bits/stdc++.h>
#define ing long long 
typedef long long ll;
using namespace std;
const int N=510,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 ans=1;
	for(int i=1;i<=K;i++){
		if(!A[i][i]){
			for(int j=i+1;j<=K;j++){
				if(A[j][i]){
					ans*=-1;
					for(int k=1;k<=n;k++)
						swap(A[i][k],A[j][k]);
					break;
				}
			}
		}
		if(!A[i][i])return 0;
		for(int j=i+1;j<=K;j++){
			if(A[j][i]>A[i][i]){
				ans*=-1;
				for(int k=1;k<=K;k++)
					swap(A[i][k],A[j][k]);
			}
			while(A[j][i]){
				ll tmp=A[i][i]*power(A[j][i],mod-2)%mod;
				for(int k=1;k<=K;k++)
					A[i][k]=(A[i][k]-tmp*A[j][k]%mod+mod)%mod;
				ans*=-1;
				for(int k=1;k<=K;k++)
					swap(A[i][k],A[j][k]);
			}
			for(int k=1;k<=K;k++)A[j][k]%=mod;
		}
	}
	ans=(ans+mod)%mod;
	for(int i=1;i<=K;i++)ans=(ans*A[i][i]%mod+mod)%mod;
	return ans;
}

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);
			A[i][j]=C(x+y,x);
		}
	printf("%lld\n",Guess());
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 19508kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 20588kb

input:

2 2 2

output:

20

result:

ok 1 number(s): "20"

Test #3:

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

input:

2 3 4

output:

490

result:

ok 1 number(s): "490"

Test #4:

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

input:

1 2 8

output:

45

result:

ok 1 number(s): "45"

Test #5:

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

input:

1 10 2

output:

66

result:

ok 1 number(s): "66"

Test #6:

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

input:

9 5 7

output:

371850968

result:

ok 1 number(s): "371850968"

Test #7:

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

input:

3 3 1

output:

20

result:

ok 1 number(s): "20"

Test #8:

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

input:

7 7 9

output:

166345303

result:

ok 1 number(s): "166345303"

Test #9:

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

input:

25 15 25

output:

850087558

result:

ok 1 number(s): "850087558"

Test #10:

score: -100
Wrong Answer
time: 9ms
memory: 19864kb

input:

45 59 71

output:

793769136

result:

wrong answer 1st numbers differ - expected: '659153227', found: '793769136'