QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#475687#2568. Mountainscppcppcpp3AC ✓1ms3728kbC++141.6kb2024-07-13 16:15:002024-07-13 16:15:00

Judging History

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

  • [2024-07-13 16:15:00]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3728kb
  • [2024-07-13 16:15:00]
  • 提交

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=105;
const int p=1e9+7;

static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
inline int wrd(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+c-48;c=getchar();}return x*f;}
inline void write(int x){static char buf[20];static int len=-1;if(x<0)putchar('-'),x=-x;do buf[++len]=x%10,x/=10;while(x);while(len>=0)putchar(buf[len--]+48);}

int n,m,k;
int fac[N*3],inv[N*3];

int qpow(int a,int b){
	int as=1;
	while(b){
		if(b&1) as=1ll*as*a%p;
		a=1ll*a*a%p,b>>=1;
	}
	return as;
}

void init(int n){
	fac[0]=1; for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%p;
	inv[n]=qpow(fac[n],p-2); for(int i=n;i;--i) inv[i-1]=1ll*inv[i]*i%p;
}

int C(int n,int m){
	if(n<m || m<0) return 0;
	return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;
}

int a[N][N],as=1;

signed main(){
	n=wrd(),m=wrd(),k=wrd(),init(n+m+k);
	for(int i=0;i<k;++i){ // s[i]
		for(int j=0;j<k;++j){ // t[j]
			int x=m+j-i,y=n+i-j;
			a[i][j]=C(x+y,x);
		}
	}
	
	for(int i=0;i<k;++i){
		for(int j=i;j<k;++j){
			if(!a[j][i]) continue;
			if(i^j) as=p-as,swap(a[i],a[j]);
			break; 
		}
		if(!a[i][i]){as=0;break;}
		int iv=qpow(a[i][i],p-2);
		for(int j=i+1;j<k;++j){
			if(!a[j][i]) continue;
			int tt=a[j][i];
			for(int l=i;l<k;++l){
				a[j][l]=(1ll*a[j][l]-1ll*tt*iv%p*a[i][l]%p+p)%p;	
			}
		}
	}
	for(int i=0;i<k;++i) as=1ll*as*a[i][i]%p;
	return write(as),0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3504kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

2 2 2

output:

20

result:

ok 1 number(s): "20"

Test #3:

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

input:

2 3 4

output:

490

result:

ok 1 number(s): "490"

Test #4:

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

input:

1 2 8

output:

45

result:

ok 1 number(s): "45"

Test #5:

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

input:

1 10 2

output:

66

result:

ok 1 number(s): "66"

Test #6:

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

input:

9 5 7

output:

371850968

result:

ok 1 number(s): "371850968"

Test #7:

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

input:

3 3 1

output:

20

result:

ok 1 number(s): "20"

Test #8:

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

input:

7 7 9

output:

166345303

result:

ok 1 number(s): "166345303"

Test #9:

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

input:

25 15 25

output:

850087558

result:

ok 1 number(s): "850087558"

Test #10:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

45 59 71

output:

659153227

result:

ok 1 number(s): "659153227"

Test #11:

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

input:

73 3 25

output:

683124269

result:

ok 1 number(s): "683124269"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

1 48 78

output:

446896916

result:

ok 1 number(s): "446896916"

Test #13:

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

input:

25 100 32

output:

966287506

result:

ok 1 number(s): "966287506"

Test #14:

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

input:

85 64 40

output:

125679545

result:

ok 1 number(s): "125679545"

Test #15:

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

input:

5 9 94

output:

620471576

result:

ok 1 number(s): "620471576"

Test #16:

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

input:

33 57 40

output:

637315057

result:

ok 1 number(s): "637315057"

Test #17:

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

input:

61 6 97

output:

362472796

result:

ok 1 number(s): "362472796"

Test #18:

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

input:

85 50 51

output:

192099209

result:

ok 1 number(s): "192099209"

Test #19:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

96 54 59

output:

714762612

result:

ok 1 number(s): "714762612"

Test #20:

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

input:

20 99 12

output:

772155662

result:

ok 1 number(s): "772155662"

Test #21:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

48 39 62

output:

670046604

result:

ok 1 number(s): "670046604"

Test #22:

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

input:

76 83 16

output:

976820079

result:

ok 1 number(s): "976820079"

Test #23:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

96 36 61

output:

20854557

result:

ok 1 number(s): "20854557"

Test #24:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

18 40 77

output:

261684871

result:

ok 1 number(s): "261684871"

Test #25:

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

input:

42 84 26

output:

458573307

result:

ok 1 number(s): "458573307"

Test #26:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

71 25 80

output:

875902815

result:

ok 1 number(s): "875902815"

Test #27:

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

input:

95 73 26

output:

922299967

result:

ok 1 number(s): "922299967"

Test #28:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

19 17 83

output:

494148696

result:

ok 1 number(s): "494148696"

Test #29:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

100 100 100

output:

192912055

result:

ok 1 number(s): "192912055"

Test #30:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

100 98 99

output:

412293529

result:

ok 1 number(s): "412293529"