QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474161#2568. Mountainsxbw_________AC ✓2ms5008kbC++141.3kb2024-07-12 16:25:572024-07-12 16:25:57

Judging History

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

  • [2024-07-12 16:25:57]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:5008kb
  • [2024-07-12 16:25:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn=102,mod=1e9+7;
typedef long long ll;
int n,m,k;
ll a[maxn][maxn],c[maxn<<2][maxn<<2];
ll C(ll x,ll y){
	if(x<0||y<0||x<y) return 0;
	return c[x][y];
}
int main(){
	cin>>n>>m>>k;
	c[0][0]=1;
	for(int i=1;i<=max(n,m)*4;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	} 
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++){
			//假设左上角(0,0),左下角(n,0),右上角(0,m)
			//那么左下方第i个点是(n+i-1,i-1)
			//那么右上方第j个点是(j-1,m+j-1)
			//那么你需要从n+i-1走到j-1 从m+j-1走到i-1
			//但是根据轮廓线定义 你只能往上或者左走 
			//所以你需要往上走n+i-1-(j-1)=n+i-j格 
			//所以你需要往上走m+j-1-(i-1)=m+j-i格 
			//也就是说n+i-j>=0,m+j-i>=0
			//事实上这就符合C的一种补充定义:根据组合意义 不合法值为0 
			a[i][j]=C(n+m,n+i-j);
		}
	ll res=1;
	for(int i=1;i<=k;i++){
		for(int j=i+1;j<=k;j++){
			while(a[i][i]){
				ll div=a[j][i]/a[i][i]%mod;
				for(int l=i;l<=k;l++)
					a[j][l]=((a[j][l]-div*a[i][l])%mod+mod)%mod;
				swap(a[i],a[j]);
				res=-res;
			}
			swap(a[i],a[j]);
			res=-res;
		} 
	}
	for(int i=1;i<=k;i++)
		res=res*a[i][i]%mod;
	cout<<(res%mod+mod)%mod<<'\n';
	
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

2 2 2

output:

20

result:

ok 1 number(s): "20"

Test #3:

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

input:

2 3 4

output:

490

result:

ok 1 number(s): "490"

Test #4:

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

input:

1 2 8

output:

45

result:

ok 1 number(s): "45"

Test #5:

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

input:

1 10 2

output:

66

result:

ok 1 number(s): "66"

Test #6:

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

input:

9 5 7

output:

371850968

result:

ok 1 number(s): "371850968"

Test #7:

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

input:

3 3 1

output:

20

result:

ok 1 number(s): "20"

Test #8:

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

input:

7 7 9

output:

166345303

result:

ok 1 number(s): "166345303"

Test #9:

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

input:

25 15 25

output:

850087558

result:

ok 1 number(s): "850087558"

Test #10:

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

input:

45 59 71

output:

659153227

result:

ok 1 number(s): "659153227"

Test #11:

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

input:

73 3 25

output:

683124269

result:

ok 1 number(s): "683124269"

Test #12:

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

input:

1 48 78

output:

446896916

result:

ok 1 number(s): "446896916"

Test #13:

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

input:

25 100 32

output:

966287506

result:

ok 1 number(s): "966287506"

Test #14:

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

input:

85 64 40

output:

125679545

result:

ok 1 number(s): "125679545"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

5 9 94

output:

620471576

result:

ok 1 number(s): "620471576"

Test #16:

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

input:

33 57 40

output:

637315057

result:

ok 1 number(s): "637315057"

Test #17:

score: 0
Accepted
time: 2ms
memory: 4508kb

input:

61 6 97

output:

362472796

result:

ok 1 number(s): "362472796"

Test #18:

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

input:

85 50 51

output:

192099209

result:

ok 1 number(s): "192099209"

Test #19:

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

input:

96 54 59

output:

714762612

result:

ok 1 number(s): "714762612"

Test #20:

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

input:

20 99 12

output:

772155662

result:

ok 1 number(s): "772155662"

Test #21:

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

input:

48 39 62

output:

670046604

result:

ok 1 number(s): "670046604"

Test #22:

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

input:

76 83 16

output:

976820079

result:

ok 1 number(s): "976820079"

Test #23:

score: 0
Accepted
time: 2ms
memory: 4908kb

input:

96 36 61

output:

20854557

result:

ok 1 number(s): "20854557"

Test #24:

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

input:

18 40 77

output:

261684871

result:

ok 1 number(s): "261684871"

Test #25:

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

input:

42 84 26

output:

458573307

result:

ok 1 number(s): "458573307"

Test #26:

score: 0
Accepted
time: 2ms
memory: 4628kb

input:

71 25 80

output:

875902815

result:

ok 1 number(s): "875902815"

Test #27:

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

input:

95 73 26

output:

922299967

result:

ok 1 number(s): "922299967"

Test #28:

score: 0
Accepted
time: 2ms
memory: 3952kb

input:

19 17 83

output:

494148696

result:

ok 1 number(s): "494148696"

Test #29:

score: 0
Accepted
time: 2ms
memory: 5008kb

input:

100 100 100

output:

192912055

result:

ok 1 number(s): "192912055"

Test #30:

score: 0
Accepted
time: 2ms
memory: 4928kb

input:

100 98 99

output:

412293529

result:

ok 1 number(s): "412293529"